二叉树leetcode题汇总

一、递归解法

树是一种递归结构，很多树问题都可以使用递归来处理。对应一些需要强整合的递归问题，递归解法一般是最优解。

树的高度

104 Maximum Depth of Binary Tree (Easy)

递归解法最方便，属于强整合问题。也可以采用队列来解，每一层高度加1。
平衡树

110 Balanced Binary Tree (Easy)

使用树的高度函数辅助即可，全程利用树的高度，避免多个递归函数。
两节点的最长路径

543 Diameter of Binary Tree (Easy)

使用树的高度函数辅助即可，同样是强整合。

归并两棵树

617 Merge Two Binary Trees (Easy)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if (root1 == null && root2 == null) {
            return null;
        } else if (root1 == null) {
            return root2;
        } else if (root2 == null) {
            return root1;
        } else {
            root1.val = root1.val + root2.val;
            root1.left = mergeTrees(root1.left, root2.left);
            root1.right = mergeTrees(root1.right, root2.right);
            return root1;
        }
    }

二、BST

BST 是二叉排序树：根节点大于等于左子树所有节点，小于等于右子树所有节点。

二叉查找树中序遍历有序。

考点：中序遍历有序、二叉搜索树性质（合法）

寻找二叉查找树的第 k 个元素

\230. Kth Smallest Element in a BST (Medium)

利用中序遍历迭代方式

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


	private int count = 0;

    public int kthSmallest(TreeNode root, int k) {
        ArrayDeque<TreeNode> stack = new ArrayDeque<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {
                stack.push(cur);
                cur = cur.left;
            } else {
                TreeNode node = stack.pop();
                if (++count == k) {
                    return node.val;
                }
                cur = node.right;
            }
        }
        return -1;
    }

把二叉搜索树转换为累加树

538. 把二叉搜索树转换为累加树

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


TreeNode convertBST(TreeNode root) {
    traverse(root);
    return root;
}

// 记录累加和
int sum = 0;
void traverse(TreeNode root) {
    if (root == null) {
        return;
    }
    traverse(root.right);
    // 维护累加和
    sum += root.val;
    // 将 BST 转化成累加树
    root.val = sum;
    traverse(root.left);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


    private int sum = 0;

    public TreeNode convertBST(TreeNode root) {
        ArrayDeque<TreeNode> stack = new ArrayDeque<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {
                stack.push(cur);
                cur = cur.right;
            } else {
                TreeNode node = stack.pop();
                sum += node.val;
                node.val = sum;
                cur = node.left;
            }
        }
        return root;
    }

验证二叉搜索树

98. 验证二叉搜索树

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


boolean isValidBST(TreeNode root) {
    return isValidBST(root, null, null);
}

/* 限定以 root 为根的子树节点必须满足 max.val > root.val > min.val */
boolean isValidBST(TreeNode root, TreeNode min, TreeNode max) {
    // base case
    if (root == null) return true;
    // 若 root.val 不符合 max 和 min 的限制，说明不是合法 BST
    if (min != null && root.val <= min.val) return false;
    if (max != null && root.val >= max.val) return false;
    // 限定左子树的最大值是 root.val，右子树的最小值是 root.val
    return isValidBST(root.left, min, root) 
        && isValidBST(root.right, root, max);
}

我们通过使用辅助函数，增加函数参数列表，在参数中携带额外信息，将这种约束传递给子树的所有节点，这也是二叉树算法的一个小技巧吧。

修剪二叉查找树

669. 修剪二叉搜索树

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


public TreeNode trimBST(TreeNode root, int low, int high) {
    if (root == null)
        return null;
    if (root.val < low) {
        return trimBST(root.right, low, high);
    } else if (root.val > high) {
        return trimBST(root.left, low, high);
    } else {
        root.left = trimBST(root.left, low, high);
        root.right = trimBST(root.right, low, high);
        return root;
    }
}

二叉查找树的最近公共祖先

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    int min = Math.min(p.val, q.val);
    int max = Math.max(p.val, q.val);
    while (root != null) {
        if (root.val > max) {
            root = root.left;
        } else if(root.val < min) {
            root = root.right;
        } else {
            return root;
        }
    }
    return null;
}

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root.val > p.val && root.val > q.val)
        return lowestCommonAncestor(root.left, p, q);
    if (root.val < p.val && root.val < q.val)
        return lowestCommonAncestor(root.right, p, q);
    return root;
}

用 Git 来讲讲二叉树最近公共祖先

236. 二叉树的最近公共祖先

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q)
        return root;
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    if (left == null)
        return right;
    if (right == null)
        return left;
    return root;
}

二叉树的序列号与反序列化

297. 二叉树的序列化与反序列化

 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


public class Codec {

    String SEP = ",";
    String NULL = "#";

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        serialize(root, sb);
        return sb.toString();
    }

    private void serialize(TreeNode root, StringBuilder sb) {
        if (root == null) {
            sb.append(NULL).append(SEP);
            return;
        }
        sb.append(root.val).append(SEP);
        serialize(root.left, sb);
        serialize(root.right, sb);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        LinkedList<String> nodes = new LinkedList<>();
        nodes.addAll(Arrays.asList(data.split(SEP)));
        return deserialize(nodes);
    }

    private TreeNode deserialize(LinkedList<String> nodes) {
        String val = nodes.removeFirst();
        if (val.equals(NULL)) {
            return null;
        }
        TreeNode root = new TreeNode(Integer.valueOf(val));
        root.left = deserialize(nodes);
        root.right = deserialize(nodes);
        return root;
    }
}

二叉搜索子树的最大键值和

1373. 二叉搜索子树的最大键值和

有冗余信息，可以优化，为了记录一下自己写的

 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


class Solution {
    int maxSum = 0;
    public int maxSumBST(TreeNode root) {
        int[] res = helper(root);
        return maxSum;
    }

    private int[] helper(TreeNode root) {
        int[] res = new int[4];
        if (root == null) {
            res[1] = 1;
            return res;
        }
        int[] left = helper(root.left);
        int[] right = helper(root.right);
        if (left[1] == 0 || right[1] == 0) {
            res[1] = 0;
            res[0] = Math.max(left[0], right[0]);
            if (res[0] < 0) {
                res[0] = 0;
                return res;
            }
            return res;
        }
        int leftMin = left[2];
        int leftMax = left[3];
        int rightMin = right[2];
        int rightMax = right[3];
        if ((root.val > leftMax || root.left == null) && (root.val < rightMin || root.right == null)) {
            res[1] = 1;
            res[0] = left[0] + right[0] + root.val;

            if (root.left == null && root.right == null) {
                res[2] = root.val;
                res[3] = root.val;
            } else if (root.left == null) {
                res[2] = root.val;
                res[3] = rightMax;
            } else if (root.right == null) {
                res[2] = leftMin;
                res[3] = root.val;
            } else {
                res[2] = leftMin;
                res[3] = rightMax;
            }
        } else {
            res[1] = 0;
            res[0] = Math.max(left[0], right[0]);
        }
        maxSum = Math.max(maxSum, res[0]);
        return res;
    }
}

 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


class Solution {
    int maxSum = 0;
    public int maxSumBST(TreeNode root) {
        traverse(root);
        return maxSum;
    }

    int[] traverse(TreeNode root) {
        // base case
        if (root == null) {
            return new int[] {
                1, Integer.MAX_VALUE, Integer.MIN_VALUE, 0
            };
        }

        // 递归计算左右子树
        int[] left = traverse(root.left);
        int[] right = traverse(root.right);

        /******* 后序遍历位置 *******/
        int[] res = new int[4];
        // 这个 if 在判断以 root 为根的二叉树是不是 BST
        if (left[0] == 1 && right[0] == 1 &&
            root.val > left[2] && root.val < right[1]) {
            // 以 root 为根的二叉树是 BST
            res[0] = 1;
            // 计算以 root 为根的这棵 BST 的最小值
            res[1] = Math.min(left[1], root.val);
            // 计算以 root 为根的这棵 BST 的最大值
            res[2] = Math.max(right[2], root.val);
            // 计算以 root 为根的这棵 BST 所有节点之和
            res[3] = left[3] + right[3] + root.val;
            // 更新全局变量
            maxSum = Math.max(maxSum, res[3]);
        } else {
            // 以 root 为根的二叉树不是 BST
            res[0] = 0;
            // 其他的值都没必要计算了，因为用不到
        }
        /**************************/

        return res;
    }
}