深度遍历
# 94. 二叉树的中序遍历 (opens new window)
左子节点先全部入栈；
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> ret = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
if(root==null) return ret;
TreeNode cur = root;
while(cur!=null || !stack.isEmpty()){
if(cur!=null){
stack.push(cur);
cur = cur.left;
}else{
cur = stack.pop();
ret.add(cur.val);
cur = cur.right;
}
}
return ret;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 144. 二叉树的前序遍历 (opens new window)
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> ret = new ArrayList<>();
if(root==null){
return ret;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode cur = stack.pop();
ret.add(cur.val);
if(cur.right!=null){
stack.push(cur.right);
}
if(cur.left!=null){
stack.push(cur.left);
}
}
return ret;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 145. 二叉树的后序遍历 (opens new window)
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> ret = new ArrayList<>();
if(root==null){
return ret;
}
Stack<TreeNode> stack = new Stack<>();
stack.add(root);
while(!stack.isEmpty()){
TreeNode cur = stack.pop();
ret.add(cur.val);
if(cur.left!=null){
stack.push(cur.left);
}
if(cur.right!=null){
stack.push(cur.right);
}
}
Collections.reverse(ret);
return ret;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 653. 两数之和 IV (opens new window)
class Solution {
Set<Integer> set = new HashSet<>();
public boolean findTarget(TreeNode root, int k) {
if(root==null) return false;
if(set.contains(k-root.val)) return true;
set.add(root.val);
return findTarget(root.left,k) || findTarget(root.right,k);
}
}
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
# 543. 二叉树的直径 (opens new window)
class Solution {
int ans;
public int diameterOfBinaryTree(TreeNode root) {
dfs(root);
return ans;
}
int dfs(TreeNode root){
if(root==null) return 0;
int l = dfs(root.left);
int r = dfs(root.right);
ans = Math.max(l+r,ans);
return 1+Math.max(l,r);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
# 124. 二叉树中的最大路径和 (opens new window)
class Solution {
int ans = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
if(root==null) return 0;
dfs(root);
return ans;
}
int dfs(TreeNode root){
if(root==null) return 0;
int l = Math.max(0,dfs(root.left));
int r = Math.max(0,dfs(root.right));
ans = Math.max(ans,root.val+l+r);
return root.val+Math.max(l,r);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 236. 二叉树的最近公共祖先 (opens new window)
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
return dfs(root,p.val,q.val);
}
TreeNode dfs(TreeNode root,int v1,int v2){
if(root==null) return null;
if(root.val==v1 || root.val==v2){
return root;
}
TreeNode l = dfs(root.left,v1,v2);
TreeNode r = dfs(root.right,v1,v2);
if(l!=null && r!=null){
return root;
}
return l!=null?l:r;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 230. 二叉搜索树中第K小的元素 (opens new window)
class Solution {
int res;
int rank;
public int kthSmallest(TreeNode root, int k) {
dfs(root,k);
return res;
}
void dfs(TreeNode root,int k){
if(root==null) return ;
dfs(root.left,k);
rank++;
if(rank==k){
res = root.val;
return ;
}
dfs(root.right,k);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 226. 翻转二叉树 (opens new window)
class Solution {
public TreeNode invertTree(TreeNode root) {
if(root==null){
return null;
}
TreeNode lson = invertTree(root.left);
TreeNode rson = invertTree(root.right);
root.left = rson;
root.right = lson;
return root;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12
# 101. 对称二叉树 (opens new window)
class Solution {
public boolean isSymmetric(TreeNode root) {
if(root==null) return true;
return dfs(root.left,root.right);
}
boolean dfs(TreeNode lson,TreeNode rson){
if(lson==null&&rson==null)
return true;
if(lson!=null&&rson==null || lson==null&&rson!=null)
return false;
if(lson.val!=rson.val)
return false;
boolean outside = dfs(lson.left,rson.right);
boolean inside = dfs(lson.right,rson.left);
return outside&&inside;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 104. 二叉树的最大深度 (opens new window)
class Solution {
public int maxDepth(TreeNode root) {
if(root==null) return 0;
int lson = maxDepth(root.left);
int rson = maxDepth(root.right);
return Math.max(lson,rson)+1;
}
}
1
2
3
4
5
6
7
8
2
3
4
5
6
7
8
# 111. 二叉树的最小深度 (opens new window)
class Solution {
public int minDepth(TreeNode root) {
if(root==null) return 0;
int lson = minDepth(root.left);
int rson = minDepth(root.right);
if(root.left==null)
return rson+1;
if(root.right==null)
return lson+1;
return Math.min(lson,rson)+1;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12
# 222. 完全二叉树的节点个数 (opens new window)
class Solution {
public int countNodes(TreeNode root) {
if(root==null) return 0;
int lson = countNodes(root.left);
int rson = countNodes(root.right);
return lson+rson+1;
}
}
1
2
3
4
5
6
7
8
2
3
4
5
6
7
8
# 110. 平衡二叉树 (opens new window)
class Solution {
public boolean isBalanced(TreeNode root) {
if(root==null) return true;
return Math.abs(getDepth(root.left)-getDepth(root.right))<=1
&& isBalanced(root.left) && isBalanced(root.right);
}
int getDepth(TreeNode root){
if(root==null) return 0;
return Math.max(getDepth(root.left),getDepth(root.right))+1;
}
}
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
# 404. 左叶子之和 (opens new window)
class Solution {
public int sumOfLeftLeaves(TreeNode root) {
if(root==null) return 0;
int lson = sumOfLeftLeaves(root.left);
int rson = sumOfLeftLeaves(root.right);
int tmp = 0;
if(root.left!=null && root.left.left==null && root.left.right==null){
tmp += root.left.val;
}
return tmp+lson+rson;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12
# 513. 找树左下角的值 (opens new window)
class Solution {
int deep = -1;
int ret = 0;
public int findBottomLeftValue(TreeNode root) {
ret = root.val;
dfs(root,0);
return ret;
}
void dfs(TreeNode root,int d){
if(root==null) return ;
if(root.left==null&&root.right==null){
if(d>deep){
deep = d;
ret = root.val;
}
}
if(root.left!=null){
dfs(root.left,d+1);
}
if(root.right!=null){
dfs(root.right,d+1);
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 700. 二叉搜索树中的搜索 (opens new window)
class Solution {
public TreeNode searchBST(TreeNode root, int val) {
if(root==null || root.val==val) return root;
if(root.val<val) return searchBST(root.right,val);
return searchBST(root.left,val);
}
}
1
2
3
4
5
6
7
2
3
4
5
6
7
# 98. 验证二叉搜索树 (opens new window)
class Solution {
public boolean isValidBST(TreeNode root) {
return dfs(root,null,null);
}
boolean dfs(TreeNode root,TreeNode minNode,TreeNode maxNode){
if(root==null) return true;
if(minNode!=null && minNode.val>=root.val){
return false;
}
if(maxNode!=null && maxNode.val<=root.val){
return false;
}
return dfs(root.left,minNode,root) &&
dfs(root.right,root,maxNode);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 530. 二叉搜索树的最小绝对差 (opens new window)
class Solution {
TreeNode pre = null;
int ret = Integer.MAX_VALUE;
public int getMinimumDifference(TreeNode root) {
if(root==null) return 0;
getMinimumDifference(root.left);
if(pre!=null && root.val-pre.val<ret){
ret = root.val-pre.val;
}
pre = root;
getMinimumDifference(root.right);
return ret;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
# 114. 二叉树展开为链表 (opens new window)
class Solution {
public void flatten(TreeNode root) {
if(root==null) return ;
flatten(root.left);
flatten(root.right);
TreeNode l = root.left;
TreeNode r = root.right;
root.left = null;
root.right = l;
TreeNode p = root;
while(p.right!=null){
p = p.right;
}
p.right = r;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 863. 二叉树中所有距离为 K 的结点 (opens new window)
class Solution {
Map<Integer,TreeNode> parents = new HashMap<>();
List<Integer> ret = new ArrayList<>();
public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
findParents(root);
findAns(target,null,0,k);
return ret;
}
void findParents(TreeNode node){
if(node.left!=null){
parents.put(node.left.val,node);
findParents(node.left);
}
if(node.right!=null){
parents.put(node.right.val,node);
findParents(node.right);
}
}
void findAns(TreeNode node,TreeNode from,int dist,int k){
if(node==null)
return ;
if(dist==k){
ret.add(node.val);
return ;
}
if(node.left!=from)
findAns(node.left,node,dist+1,k);
if(node.right!=from)
findAns(node.right,node,dist+1,k);
if(parents.get(node.val)!=from)
findAns(parents.get(node.val),node,dist+1,k);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33