二叉树中和为某一值的路径
题目描述
思路
DFS
没有什么要注意的，就是单纯的DFS的使用
代码实现
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private Stack<Integer> s = null;
private List<List<Integer>> result=null;
public List<List<Integer>> pathSum(TreeNode root, int target) {
s = new Stack<Integer>();
result=new ArrayList<List<Integer>>();
getPath(root,target,0);
return result;
}
public void getPath(TreeNode node,int target,int sum){
if(node==null){
return;
}
sum+=node.val;
s.push(node.val);
if(sum==target&&node.left==null&&node.right==null){
result.add(new ArrayList<Integer>(s));
}
getPath(node.left,target,sum);
getPath(node.right,target,sum);
s.pop();
return ;
}
}
复杂度分析
时间复杂度
O(N)
空间复杂度
O(N)，一条线的情况
反思不足
思路
二叉搜索树和双向链表
题目描述
思路
中序遍历
本题的本质就是按二叉搜索树的中序遍历顺序构建一个循环链表，题目描述说得有些云里雾里
代码实现
class Solution {
Node pre, head;
public Node treeToDoublyList(Node root) {
if(root == null) return null;
dfs(root);
head.left = pre;
pre.right = head;
return head;
}
void dfs(Node cur) {
if(cur == null) return;
dfs(cur.left);
if(pre != null) pre.right = cur;
else head = cur;
cur.left = pre;
pre = cur;
dfs(cur.right);
}
}
复杂度分析
时间复杂度
O(N)
空间复杂度
O(N)
反思不足
思路
其实既然是要依托于中序遍历，那么就可以尝试在遍历的时候一并实现我们的需求。
二叉搜索树的第k大节点
题目描述
思路
中序遍历+先右节点
因为本题是找第k大的值，如果我们按照左根右的话只方便我们找第k小的值，但反过来右根左，就方便我们找第k大的值了
代码实现
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
int cth=0,result=0;
public int kthLargest(TreeNode root, int k) {
if(root!=null&&cth!=k){
kthLargest(root.right,k);
if(++cth==k){
result = root.val;
}
kthLargest(root.left,k);
}
return result;
}
}
复杂度分析
时间复杂度
O(N)
空间复杂度
O(N)