二叉树

发表于 | 分类于

Leetcode

104. Maximum Depth of Binary Tree

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.

For example:
Given binary tree [3,9,20,null,null,15,7],

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

return its depth = 3.

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        
        //+1是当前的节点
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}

111. Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

解题思路:

与上一题不同之处在于：找最小距离要注意，可能存在左右子树为空的情况，此时值就为0，但显然值是不为0的（只有当二叉树为空才为0），所以，在这里注意一下即可！

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int minDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        int left = minDepth(root.left);
        int right = minDepth(root.right);
        return (left == 0 || right == 0) ? left+right+1 : Math.min(left, right) + 1;
    }
}

226. Invert Binary Tree

Invert a binary tree.

1
2
3
4
5
     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
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root == null){
            return root;
        }
        
        TreeNode temp = root.left;
        root.left = invertTree(root.right);
        root.right = invertTree(temp);
        
        return root;
    }
}

100. Same Tree

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null){
            return true;
        }
        
        if(p != null && q != null){
            return isSameTree(p.left, q.left) && isSameTree(p.right, q.right) && p.val == q.val;
        }
        
        return false;
    }
}

101. Symmetric Tree

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null){
            return true;
        }
        return helper(root.left, root.right);
    }
    
    public boolean helper(TreeNode l, TreeNode r){
        if(l == null && r == null){
            return true;
        }
        if(l != null && r != null){
            return l.val == r.val && helper(l.left, r.right) && helper(l.right, r.left);
        }
        
        return false;
    }
}

222. Count Complete Tree Nodes

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
class Solution {
    public int countNodes(TreeNode root) {
        if(root == null){
            return 0;
        }
        
        int lHeight = height(root.left);
        int rHeight = height(root.right);
        if(lHeight == rHeight){
            return (1 << lHeight) + countNodes(root.right);
        }
        else{
            return (1 << rHeight) + countNodes(root.left);
        }
    }
    
    private int height(TreeNode node){
        if(node == null){
            return 0;
        }
        return 1 + height(node.left);
    }
}

110. Balanced Binary Tree

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root == null){
            return true;
        }
        
        return helper(root, 0) != -1;
    }
    
    int helper(TreeNode node, int height){
        if(node == null){
            return height;
        }
        
        int lHeight = helper(node.left, height + 1);
        int rHeight = helper(node.right, height + 1);
        
        if(Math.abs(lHeight - rHeight) > 1){
            return -1;
        }
        
        return Math.max(lHeight, rHeight);
    }
}

112. Path Sum

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.

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

return 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
class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if(root == null){
            return false;
        }
        
        if(root.left == null && root.right == null){
            return root.val == sum;
        }
        
        sum -= root.val;
        
        return hasPathSum(root.left, sum) ||
                hasPathSum(root.right, sum);
        
    }
}

404. Sum of Left Leaves

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

Example:

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        if(root == null){
            return 0;
        }
        
        int res = 0;
        if(root.left != null){
            if(root.left.left == null && root.left.right == null){
                res += root.left.val;
            }
            else{
                res += sumOfLeftLeaves(root.left);
            }
        }
        
        res += sumOfLeftLeaves(root.right);
        
        return res;
    }
}

257. Binary Tree Paths

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

Example:

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
class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new LinkedList<String>();
        
        if(root == null){
            return res;
        }
        
        if(root.left == null && root.right == null){
            res.add(String.valueOf(root.val));
            return res;
        }
        
        List<String> leftS = binaryTreePaths(root.left);
        for(int i = 0; i < leftS.size(); ++i){
            res.add(String.valueOf(root.val) + "->" + leftS.get(i));
        }
        
        List<String> rightS = binaryTreePaths(root.right);
        for(int i = 0; i < rightS.size(); ++i){
            res.add(String.valueOf(root.val) + "->" + rightS.get(i));
        }
        
        return res;
    }
}

113. Path Sum II

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

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]
]

解题思路:

深度优先搜索策略

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
class Solution {
    private List<List<Integer>> list2 = new ArrayList<List<Integer>>();
    
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        if(root == null){
            return list2;
        }
        helper(root, sum, new Stack<Integer>());
        return list2;
    }
    
    private void helper(TreeNode node, int sum, Stack<Integer> stack){
        stack.push(node.val);
        
        if(node.left == null && node.right == null){
            if(node.val == sum){
                list2.add(new ArrayList<Integer>(stack));
            }
        }
        if(node.left != null){
            helper(node.left, sum - node.val, stack);
        }
        if(node.right != null){
            helper(node.right, sum - node.val, stack);
        }
        
        stack.pop();
    }
}

129. Sum Root to Leaf Numbers

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

Example:

1
2
3
  1
 / \
2   3

The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.

Return the sum = 12 + 13 = 25.

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
class Solution {
    List<List<Integer>> list2 = new ArrayList<List<Integer>>();
    
    public int sumNumbers(TreeNode root) {
        if(root == null){
            return 0;
        }
        
        helper(root, new Stack<Integer>());
        
        int res = 0;
        for(List<Integer> l : list2){
            int sum = 0;
            int factor = 1;
            for(int i = l.size() - 1; i >= 0; --i){
                sum += factor * l.get(i);
                factor *= 10;
            }
            res += sum;
        }
        
        return res;
    }
    
    public void helper(TreeNode root, Stack<Integer> stack){
        stack.push(root.val);
        
        if(root.left == null && root.right == null){
            list2.add(new ArrayList<Integer>(stack));
        }
        if(root.left != null){
            helper(root.left, stack);
        }
        if(root.right != null){
            helper(root.right, stack);
        }
        
        stack.pop();
    }
}

437. Path Sum III

ou are given a binary tree in which each node contains an integer value.

Find the number of paths that sum to a given value.

The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1
Return 3. The paths that sum to 8 are:
1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11
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
class Solution {
    public int pathSum(TreeNode root, int sum) {
        if(root == null){
            return 0;
        }
        
        int res = helper(root, sum);
        res += pathSum(root.left, sum);
        res += pathSum(root.right, sum);
        
        return res;
    }
    
    private int helper(TreeNode node, int remain){
        if(node == null){
            return 0;
        }
        
        int res = 0;
        if(node.val == remain){
            res = 1;
        }
        
        res += (helper(node.left, remain - node.val) + helper(node.right, remain - node.val) );
         
        
        return res;
    }
}

235. Lowest Common Ancestor of a Binary Search Tree

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

Example:

1
2
3
4
5
6
7
     _______6______
    /              \
 ___2__          ___8__
/      \        /      \
0      _4       7       9
      /  \
      3   5

For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null){
            return null;
        }
        
        if(root.val < p.val && root.val < q.val){
            return lowestCommonAncestor(root.right, p, q);
        }
        
        else if(root.val > p.val && root.val > q.val){
            return lowestCommonAncestor(root.left, p, q);
        }
        
        return root;
        
    }
}

98. Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST).

Example:

1
2
3
4
  2
 / \
1   3
return true
1
2
3
4
  1
 / \
2   3
return false
1
2
3
4
5
6
7
8
9
10
11
12
13
public boolean isValidBST(TreeNode root) {
        return helper(root, null, null);
    }
    
    boolean helper(TreeNode root, Integer min, Integer max) {
        if (root == null)
            return true;
        
        if ((min != null && root.val <= min) || (max != null && root.val >= max))
            return false;
        
        return helper(root.left, min, root.val) && helper(root.right, root.val, max);
    }

450. Delete Node in a BST

Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.

Note: Time complexity should be O(height of 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
root = [5,3,6,2,4,null,7]
key = 3
    5
   / \
  3   6
 / \   \
2   4   7
Given key to delete is 3. So we find the node with value 3 and delete it.
One valid answer is [5,4,6,2,null,null,7], shown in the following BST.
    5
   / \
  4   6
 /     \
2       7
Another valid answer is [5,2,6,null,4,null,7].
    5
   / \
  2   6
   \   \
    4   7

108. Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

Example:

1
2
3
4
5
6
7
8
9
Given the sorted array: [-10,-3,0,5,9],
One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:
      0
     / \
   -3   9
   /   /
 -10  5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        if(nums == null){
            return null;
        }
        
        return helper(nums, 0, nums.length-1);
    }
    
    private TreeNode helper(int []A, int lo, int hi){
        if(lo > hi){
            return null;
        }
        
        int mid = (lo + hi) / 2;
        TreeNode node = new TreeNode(A[mid]);
        node.left = helper(A, lo, mid-1);
        node.right = helper(A, mid+1, hi);
        
        return node;
    }
}

230. Kth Smallest Element in a BST

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Note:

You may assume k is always valid, 1 ≤ k ≤ BST’s total elements.

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
class Solution 
{   private static int count = 0;
    private static int res = 0;
    public int kthSmallest(TreeNode root, int k) {
        if(root == null){
            return 0;
        }
        
        count = k;
        
        helper(root, k);
        
        return res;
    }
 
    public void helper(TreeNode node, int k){
        if(node.left != null){
            helper(node.left, k);
        }
        
        if(--count == 0){
            res = node.val;
            return;
        }
        
        if(node.right != null){
            helper(node.right, count);
        }
    }
}

236. Lowest Common Ancestor of a Binary Tree

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

1
2
3
4
5
6
7
     _______3______
    /              \
 ___5__          ___1__
/      \        /      \
6      _2       0       8
      /  \
      7   4

Example:

the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

1
2