leetcode-二叉树

发表于 | 分类于

1. Maximum Depth of Binary Tree(104)

二叉树的最大深度

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        
        return Math.max( maxDepth(root.left), maxDepth(root.right) ) + 1;
    }
}

2. Invert Binary Tree(226)

翻转二叉树

1
2
3
4
5
6
Invert a binary tree.
     4
   /   \
  2     7
 / \   / \
1   3 6   9

to

1
2
3
4
5
     4
   /   \
  7     2
 / \   / \
9   6 3   1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if( root == null ){
            return null;
        }
        
        TreeNode tmp = root.left;
        root.left = invertTree( root.right );
        root.right = invertTree( tmp );
        
        return root;
    }
    
}

3. Same Tree(100)

相同二叉树

Given two binary trees, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical and the nodes have the same value.

Example 1:

1
2
3
4
5
6
7
Input:     1         1
          / \       / \
         2   3     2   3
        [1,2,3],   [1,2,3]
Output: true

Example 2:

1
2
3
4
5
6
7
Input:     1         1
          /           \
         2             2
        [1,2],     [1,null,2]
Output: false

Example 3:

1
2
3
4
5
6
7
Input:     1         1
          / \       / \
         2   1     1   2
        [1,2,1],   [1,1,2]
Output: false
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null){
            return true;
        }
        else if( p != null && q != null){
            return p.val == q.val && isSameTree( p.left, q.left ) && isSameTree( p.right, q.right );
        }
        else{
            return false;
        }
    }
}

4. Symmetric Tree(101)

对称二叉树

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

1
2
3
4
5
    1
   / \
  2   2
 / \ / \
3  4 4  3

But the following [1,2,2,null,3,null,3] is not:

1
2
3
4
5
  1
 / \
2   2
 \   \
 3    3

Note:
Bonus points if you could solve it both recursively and iteratively.

递归版

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null){
            return true;
        }
        return helper(root.left, root.right);
    }
    
    private boolean helper(TreeNode l, TreeNode r){
        if(l == null && r == null){
            return true;
        }
        else if(l == null || r == null){
            return false;
        }
        return l.val == r.val && helper(l.left, r.right) && helper(l.right, r.left);
    }
}

迭代版

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
    	//Q1和Q2以root为中心
    	//将二叉树一分为二,
    	//root以左的节点左至右顺序入队
    	//root以右的节点右至左顺序入队
    	//相当于对称方向的层序遍历二叉树
        Queue<TreeNode> Q1 = new LinkedList<TreeNode>();
        Queue<TreeNode> Q2 = new LinkedList<TreeNode>();
        
        if(root == null){
            return true;
        }
        Q1.add(root.left);
        Q2.add(root.right);
        while(!Q1.isEmpty() && !Q2.isEmpty()){
            int size1 = Q1.size();
            int size2 = Q2.size();
            if(size1 != size2){
                return false;
            }
            for(int i = 0; i < size1; ++i){
                TreeNode n1 = Q1.remove();
                TreeNode n2 = Q2.remove();
                if(n1 == null && n2 == null){
                    continue;
                }
                if(n1 == null || n2 == null || n1.val != n2.val){
                    return false;
                }
                Q1.add(n1.left);
                Q1.add(n1.right);
                Q2.add(n2.right);
                Q2.add(n2.left);
            }
        }
        return Q1.isEmpty() && Q2.isEmpty();
    }
}

5. Count Complete Tree Nodes(222)

完全二叉树

Given a complete binary tree, count the number of nodes.

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int countNodes(TreeNode root) {
        if(root == null){
            return 0;
        }
        
        int leftHeight = height(root.left);
        int rightHeight = height(root.right);
        if(leftHeight == rightHeight){
            return (1 << leftHeight) + countNodes(root.right);
        }
        else{
            return (1 << rightHeight) + countNodes(root.left);
        }
    }
    
    private int height(TreeNode node){
        if(node == null){
            return 0;
        }
        return 1 + height(node.left);
    }
}

6. Balanced Binary Tree(110)

平衡二叉树

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 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
25
26
27
28
29
30
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root == null){
            return true;
        }
        return helper(root, 0) >= 0;
    }
    
    //自底往上进行判断
    private int helper(TreeNode root, int height){
        if(root == null){
            return height;
        }
        int leftHeight = helper(root.left, height+1);
        int rightHeight = helper(root.right, height+1);
        if(Math.abs(leftHeight - rightHeight) > 1){
            return -1;
        }
        return Math.max(leftHeight, rightHeight);
    }
}

7. Path Sum(112)

根节点到叶节点的路径和

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:
Given the below binary tree and sum = 22,

1
2
3
4
5
6
7
      5
     / \
    4   8
   /   / \
  11  13  4
 /  \      \
7    2      1

eturn true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if(root == null){
            return false;
        }
        if(root.left == null && root.right == null){
            return sum == root.val;
        }
        
        int remain = sum - root.val;
        
        return hasPathSum(root.left, remain)
                || hasPathSum(root.right, remain);
    }
}

8. Sum of Left Leaves(404)

二叉树左叶节点的和

Find the sum of all left leaves in a given binary tree.

Example:

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
34
35
36
37
3
   / \
  9  20
    /  \
   15   7
There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24.
```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        if(root == null){
            return 0;
        }
        int ret = 0;
        if(root.left != null){
            if(root.left.left == null && root.left.right == null){
                ret = root.left.val;
            }
            else{
                ret = sumOfLeftLeaves(root.left);
            }
        }
        ret += sumOfLeftLeaves(root.right);
        
        return ret;
    }
}

9. Binary Tree Paths(257)

返回二叉树的路径

Given a binary tree, return all root-to-leaf paths.

For example, given the following binary tree:

1
2
3
4
5
   1
 /   \
2     3
 \
  5

All root-to-leaf paths are:

1
["1->2->5", "1->3"]
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
34
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> ret = new ArrayList<String>();
        
        if(root == null){
            return ret;
        }
        
        if(root.left == null && root.right == null){
            ret.add( String.valueOf(root.val));
        }
        //把当前节点，接到每条路径上
        List<String> LList = binaryTreePaths(root.left);
        for(int i = 0 ; i < LList.size(); ++i){
            ret.add(root.val + "->" + LList.get(i));
        }
            
        List<String> RList = binaryTreePaths(root.right);
        for(int i = 0; i < RList.size(); ++i){
            ret.add(root.val + "->" + RList.get(i));
        }
        
        return ret;
    }
}

10. Path Sum II(113)

Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.

For example:
Given the below binary tree and sum = 22,

1
2
3
4
5
6
7
      5
     / \
    4   8
   /   / \
  11  13  4
 /  \    / \
7    2  5   1

return

1
2
3
4
[
   [5,4,11,2],
   [5,8,4,5]
]