算法技巧-二叉树

98. 验证二叉搜索树

易错题目：

/**
 * 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 {
//     public boolean isValidBST(TreeNode root) {
//         if (null == root) {
//             return true;
//         }

//         if (null != root.left && (root.left.val >= root.val || !isValidBST(root.left))) {
//             return false;
//         }

//         if (null != root.right && (root.right.val <= root.val || !isValidBST(root.right))) {
//             return false;
//         }

//         return true;
//     }


// }

// 错误代码

class Solution {

    private boolean res = true;
    private long preValue = Long.MIN_VALUE;

    public boolean isValidBST(TreeNode root) {
        midOrder(root);
        return res;
    }

    private void midOrder(TreeNode root) {

        if (!res) {
            return;
        }

        if (null != root) {
            midOrder(root.left);

            if (preValue >= root.val) {
                res = false;
                return;
            }

            preValue = Long.valueOf(root.val);

            midOrder(root.right);
        }
    }


}

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

100. 相同的树

/**
 * 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 {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        return dfs(p, q);
    }

    private boolean dfs(TreeNode p, TreeNode q) {
        
        if (null == p && null == q) {
            return true;
        }

        if (null == p) {
            return false;
        }

        if (null == q) {
            return false;
        }

        if (p.val != q.val) {
            return false;
        }

        return dfs(p.left, q.left) && dfs(p.right, q.right);
    }
}
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

572. 另一棵树的子树

class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {

        if (null == root && null == subRoot) {
            return true;
        }

        if (null == root) {
            return false;
        }

        if (null == subRoot) {
            return false;
        }

        return isSameTree(root, subRoot) || isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
        
    }

    private boolean isSameTree(TreeNode p, TreeNode q) {

        if (null == p && null == q) {
            return true;
        }
        if (null == p || null == q) {
            return false;
        }
        if (p.val != q.val) {
            return false;
        }
        
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
} 
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

113. 路径总和 II

二叉树回溯

/**
 * 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 {
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        Deque<Integer> path = new ArrayDeque<>();
        List<List<Integer>> res = new ArrayList<>();
        dfs(root, targetSum, path, res);
        return res;
    }

    private void dfs(TreeNode root, int targetSum, Deque<Integer> path, List<List<Integer>> res) {

        if (null == root) {
            return;
        }

        if (null == root.left && null == root.right && root.val == targetSum) {
            path.addLast(root.val);
            res.add(new ArrayList<>(path));
            path.removeLast();
            return;
        }

        int temp = targetSum - root.val;
        path.addLast(root.val);
        dfs(root.left, temp, path, res);
        dfs(root.right, temp, path, res);
        path.removeLast();
    }
}
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

501. 二叉搜索树中的众数

/**
 * 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 int preCnt = 0;
    private int preValue = Integer.MAX_VALUE;
    private int ansCnt = 0;

    private void midOrder(TreeNode root, List<Integer> ans) {
        if (root != null) {

            midOrder(root.left, ans);

            if (preValue == root.val) {
                preCnt++;
            } else {
                preValue = root.val;
                preCnt = 1;
            }

            if (ans != null) {
                if (preCnt == ansCnt) {
                    ans.add(preValue);
                }
            }
            ansCnt = Math.max(ansCnt, preCnt);

            midOrder(root.right, ans);
        }

    }


    public int[] findMode(TreeNode root) {
        if (root == null) {
            return new int[0];
        }

        midOrder(root, null);

        preCnt = 0;
        List<Integer> ans = new ArrayList<>();
        midOrder(root, ans);

        return ans.stream().mapToInt(i -> i).toArray();
    }
}
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
49
50
51
52
53
54
55
56
57
58
59
60

450. 删除二叉搜索树中的节点

/**
 * 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 void swapValue(TreeNode a, TreeNode b) {
        int t = a.val;
        a.val = b.val;
        b.val = t;
    }

    public TreeNode deleteNode(TreeNode root, int key) {

        if (null == root) {
            return null;
        }

        if (key < root.val) {
            root.left = deleteNode(root.left, key);
        } else if (key > root.val) {
            root.right = deleteNode(root.right, key);
        } else {
            if (null == root.left && null == root.right) {
                return null;
            } else if (null != root.left) {
                TreeNode large = root.left;
                while (null != large.right) {
                    large = large.right;
                }
                swapValue(root, large);
                root.left = deleteNode(root.left, key);
            } else if (null == root.left && null != root.right) {
                TreeNode small = root.right;
                while (null != small.left) {
                    small = small.left;
                }
                swapValue(root, small);
                root.right = deleteNode(root.right, key);
            }
        }

        return root;
    }
}
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
49
50
51
52
53
54
55
56

701. 二叉搜索树中的插入操作

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {

        if (null == root) {
            return new TreeNode(val);
        }

        if (val < root.val) {
            root.left = insertIntoBST(root.left, val);
        } else {
            root.right = insertIntoBST(root.right, val);
        }

        return root;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

104. 二叉树的最大深度

“自顶向下” 的解决方案:

private int answer;		// don't forget to initialize answer before call maximum_depth
private void maximum_depth(TreeNode root, int depth) {
    if (root == null) {
        return;
    }
    if (root.left == null && root.right == null) {
        answer = Math.max(answer, depth);
    }
    maximum_depth(root.left, depth + 1);
    maximum_depth(root.right, depth + 1);
}
1
2
3
4
5
6
7
8
9
10
11

“自底向上” 的解决方案:

public int maximum_depth(TreeNode root) {
	if (root == null) {
		return 0;                                   // return 0 for null node
	}
	int left_depth = maximum_depth(root.left);
	int right_depth = maximum_depth(root.right);
	return Math.max(left_depth, right_depth) + 1;	// return depth of the subtree rooted at root
}
1
2
3
4
5
6
7
8

106. 从中序与后序遍历序列构造二叉树

/**
 * 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 {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return dfs(inorder, postorder);
    }

    private TreeNode dfs(int[] inorder, int[] postorder) {
        final int m = inorder.length;
        final int n = postorder.length;
        if (0 == n && 0 == m) {
            return null;
        }
        int val = postorder[n - 1];
        TreeNode root = new TreeNode(val);
        int index = findIndex(inorder, val);
        TreeNode leftNode = dfs(Arrays.copyOfRange(inorder, 0, index), 
        Arrays.copyOfRange(postorder, 0, index));
        TreeNode rightNode = dfs(Arrays.copyOfRange(inorder, index + 1, m), 
        Arrays.copyOfRange(postorder, index, n - 1));
        root.left = leftNode;
        root.right = rightNode;
        return root;
    }

    private int findIndex(int[] inorder, int target) {
        final int n = inorder.length;
        for (int i = 0; i < n; i ++) {
            if (target == inorder[i]) {
                return i;
            }
        }
        return -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
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() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return dfs(preorder, inorder);
    }

    private TreeNode dfs(int[] preorder, int[] inorder) {
        final int preLen = preorder.length;
        final int inLen = inorder.length;
        if (0 == preLen && 0 == inLen) {
            return null;
        }
        int val = preorder[0];
        int index = findIndex(inorder, val);
        TreeNode root = new TreeNode(val);
        TreeNode leftNode = dfs(Arrays.copyOfRange(preorder, 1, 1 + index), 
        Arrays.copyOfRange(inorder, 0, index));
        TreeNode rightNode = dfs(Arrays.copyOfRange(preorder, 1 + index, preLen), 
        Arrays.copyOfRange(inorder, index + 1, inLen));
        root.left = leftNode;
        root.right = rightNode;
        return root;

    }

    private int findIndex(int[] inorder, int target) {
        final int n = inorder.length;
        for (int i = 0; i < n; i ++) {
            if (target == inorder[i]) {
                return i;
            }
        }
        return -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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

116. 填充每个节点的下一个右侧节点指针

class Solution {
    public Node connect(Node root) {
        Queue<Node> queue = new LinkedList<>();
        if (null != root) {
            queue.offer(root);
        }
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i ++) {
                Node curNode = queue.poll();
                Node nextNode = null;
                if (i < size - 1) {
                    nextNode = queue.peek();
                }
                curNode.next = nextNode;
                if (null != curNode.left) {
                    queue.offer(curNode.left);
                }
                if (null != curNode.right) {
                    queue.offer(curNode.right);
                }
                
            }
        }

        return root;
    }
}
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

剑指 Offer 68 - II. 二叉树的最近公共祖先

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        if (null == root || root == p || root == q) {
            return root;
        }

        TreeNode leftNode = lowestCommonAncestor(root.left, p, q);
        TreeNode rightNode = lowestCommonAncestor(root.right, p, q);

        if (null != leftNode && null != rightNode) {
            return root;
        }

        return null == leftNode ? rightNode : leftNode;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17