CS-Notes Leetcode 树形结构题解：递归、遍历、BST 与 Trie 的体系化实战

2026-09-06 17:03:19作者：幸俭卉

本文基于 CS-Notes 仓库中的 [Leetcode 题解 - 树](https://gitcode.com/GitHub_Trending/cs/CS-Notes/blob/b70121d377cb6005eb65f12b098cd5decd905669/notes/Leetcode 题解 - 树.md?utm_source=gitcode_repo_files)，系统讲解二叉树与树形结构题目的解题体系：从递归思维的 14 道基础题，到 BFS 层次遍历、前中后序遍历的非递归实现，再到 BST 的 10 道经典题和 Trie 前缀树的完整实现。读完本文，你可以掌握“后序递归返回信息 + 全局状态记录答案”这一树题核心范式，并能独立完成 Leetcode 中树形结构相关的绝大部分题目。

树是面试中出现频率最高的数据结构之一。CS-Notes 的 Leetcode 系列将其单列为一个专题（可在 [Leetcode 题解 - 目录](https://gitcode.com/GitHub_Trending/cs/CS-Notes/blob/b70121d377cb6005eb65f12b098cd5decd905669/notes/Leetcode 题解 - 目录.md?utm_source=gitcode_repo_files) 中找到全部专题索引），下面按原文档的四大板块逐题展开，并在每题基础上补充复杂度分析与模式归纳。

一、递归：树题的第一性原理

原文档开篇即点出核心思想：

一棵树要么是空树，要么有两个指针，每个指针指向一棵树。树是一种递归结构，很多树的问题可以使用递归来处理。

这句话定义了二叉树的数据结构本质——节点持有指向左、右两棵子树的指针。由此得到树题递归模板：

// 递归三要素：1. 定义返回值语义  2. 处理当前节点  3. 递归子树并组合
Result solve(TreeNode root) {
    if (root == null) return 基线值;   // 空树
    Result left = solve(root.left);     // 左子树
    Result right = solve(root.right);  // 右子树
    return combine(root, left, right); // 组合
}

下文 14 道题几乎都能套入这个模板。

1. 树的高度（104. Maximum Depth of Binary Tree）

public int maxDepth(TreeNode root) {
    if (root == null) return 0;
    return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}

返回值语义：当前子树的高度。空树高度为 0，当前节点高度为左右子树高度较大者加 1。时间复杂度 O(n)，每个节点访问一次。

2. 平衡树（110. Balanced Binary Tree）

平衡树要求任意节点的左右子树高度差都小于等于 1。直接在每个节点上调两次 maxDepth 会退化为 O(n^2)，因此把“求高度”和“判断平衡”合并到同一次递归里，通过全局变量记录结果：

private boolean result = true;

public boolean isBalanced(TreeNode root) {
    maxDepth(root);
    return result;
}

public int maxDepth(TreeNode root) {
    if (root == null) return 0;
    int l = maxDepth(root.left);
    int r = maxDepth(root.right);
    if (Math.abs(l - r) > 1) result = false;
    return 1 + Math.max(l, r);
}

这是“一次递归同时完成两件事”的典型写法。注意判断条件中的 > 对应的是平衡树定义里“差都小于等于 1”的反面。

3. 两节点的最长路径（543. Diameter of Binary Tree）

Input:

         1
        / \
       2  3
      / \
     4   5

Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

private int max = 0;

public int diameterOfBinaryTree(TreeNode root) {
    depth(root);
    return max;
}

private int depth(TreeNode root) {
    if (root == null) return 0;
    int leftDepth = depth(root.left);
    int rightDepth = depth(root.right);
    max = Math.max(max, leftDepth + rightDepth);
    return Math.max(leftDepth, rightDepth) + 1;
}

这里是后序递归最重要的范式：返回值向上汇报“高度”，全局变量横向记录“过当前节点的最长路径”。经过每个节点的最长路径必为 leftDepth + rightDepth（边数），与历史最大值比较即可。这道题与上一题的结构完全同构，只是把“判平衡”换成了“求直径”。

4. 翻转树（226. Invert Binary Tree）

public TreeNode invertTree(TreeNode root) {
    if (root == null) return null;
    TreeNode left = root.left;  // 后面的操作会改变 left 指针，因此先保存下来
    root.left = invertTree(root.right);
    root.right = invertTree(left);
    return root;
}

先保存 root.left 再交换，否则会丢失左指针——这是原地修改树结构时最易踩的坑。该操作等价于逐层镜像翻转，与 27. 二叉树的镜像（剑指 Offer 题解）是同一问题。

5. 归并两棵树（617. Merge Two Binary Trees）

Input:
       Tree 1                     Tree 2
          1                         2
         / \                       / \
        3   2                     1   3
       /                           \   \
      5                             4   7

Output:
         3
        / \
       4   5
      / \   \
     5   4   7

public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
    if (t1 == null && t2 == null) return null;
    if (t1 == null) return t2;
    if (t2 == null) return t1;
    TreeNode root = new TreeNode(t1.val + t2.val);
    root.left = mergeTrees(t1.left, t2.left);
    root.right = mergeTrees(t1.right, t2.right);
    return root;
}

归并规则：两树同位置节点重叠时值相加，缺哪棵补哪棵。三个边界判断保证了“单边缺失时直接复用另一棵子树”的正确性，无需额外判空。

6. 判断路径和是否等于一个数（112. Path Sum）

Given the below binary tree and sum = 22,

              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.

路径和定义为从 root 到 leaf 的所有节点的和：

public boolean hasPathSum(TreeNode root, int sum) {
    if (root == null) return false;
    if (root.left == null && root.right == null && root.val == sum) return true;
    return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
}

技巧是向下递减目标值而非向上累加当前和：把 sum - root.val 作为参数传下去，到达叶子时只需比较 root.val == sum，省去了额外的累加状态。

7. 统计路径和等于一个数的路径数量（437. Path Sum III）

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

与 112 的关键区别：路径不一定以 root 开头，也不一定以 leaf 结尾，但必须连续。解法是把每个节点都当作一次“起点”，做两个递归——pathSumStartWithRoot 统计以当前节点为起点的路径数，pathSum 枚举所有起点：

public int pathSum(TreeNode root, int sum) {
    if (root == null) return 0;
    int ret = pathSumStartWithRoot(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
    return ret;
}

private int pathSumStartWithRoot(TreeNode root, int sum) {
    if (root == null) return 0;
    int ret = 0;
    if (root.val == sum) ret++;
    ret += pathSumStartWithRoot(root.left, sum - root.val) + pathSumStartWithRoot(root.right, sum - root.val);
    return ret;
}

注意这里节点值可以为负数，所以沿某条路径累加和相等后不能提前终止，必须继续向下尝试。

8. 子树（572. Subtree of Another Tree）

Given tree s:
     3
    / \
   4   5
  / \
 1   2

Given tree t:
   4
  / \
 1   2

Return true, because t has the same structure and node values with a subtree of s.

Given tree s:

     3
    / \
   4   5
  / \
 1   2
    /
   0

Given tree t:
   4
  / \
 1   2

Return false.

判断 t 是否为 s 的子树，同样拆成两个递归：“某节点能否作为匹配起点” + “枚举所有起点”：

public boolean isSubtree(TreeNode s, TreeNode t) {
    if (s == null) return false;
    return isSubtreeWithRoot(s, t) || isSubtree(s.left, t) || isSubtree(s.right, t);
}

private boolean isSubtreeWithRoot(TreeNode s, t) {
    if (t == null && s == null) return true;
    if (t == null || s == null) return false;
    if (t.val != s.val) return false;
    return isSubtreeWithRoot(s.left, t.left) && isSubtreeWithRoot(s.right, t.right);
}

isSubtreeWithRoot 要求两树结构、节点值完全一致，任一节点缺失或值不同即返回 false。该问题与 26. 树的子结构（剑指 Offer 题解）对应。

9. 树的对称（101. Symmetric Tree）

public boolean isSymmetric(TreeNode root) {
    if (root == null) return true;
    return isSymmetric(root.left, root.right);
}

private boolean isSymmetric(TreeNode t1, TreeNode t2) {
    if (t1 == null && t2 == null) return true;
    if (t1 == null || t2 == null) return false;
    if (t1.val != t2.val) return false;
    return isSymmetric(t1.left, t2.right) && isSymmetric(t1.right, t2.left);
}

双指针递归是本题的关键：比较 t1.left 与 t2.right、t1.right 与 t2.left 这两组“镜像位置”节点，交叉比较的方向不能写反。对应剑指 Offer 的 28. 对称的二叉树。

10. 最小路径（111. Minimum Depth of Binary Tree）

树的根节点到叶子节点的最小路径长度：

public int minDepth(TreeNode root) {
    if (root == null) return 0;
    int left = minDepth(root.left);
    int right = minDepth(root.right);
    if (left == 0 || right == 0) return left + right + 1;
    return Math.min(left, right) + 1;
}

易错点：不能直接 Math.min(left, right) + 1。当某一侧为空（left == 0 或 right == 0）时，叶子必须落在非空的那一侧，因此答案取 left + right + 1（此时其中一项为 0，等价于取非空侧加 1）。这与求最大深度时“空侧贡献 0 无害”的行为形成对照。

11. 统计左叶子节点的和（404. Sum of Left Leaves）

    3
   / \
  9  20
    /  \
   15   7

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

public int sumOfLeftLeaves(TreeNode root) {
    if (root == null) return 0;
    if (isLeaf(root.left)) return root.left.val + sumOfLeftLeaves(root.right);
    return sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
}

private boolean isLeaf(TreeNode node){
    if (node == null) return false;
    return node.left == null && node.right == null;
}

判定“左叶子”即 root.left 本身是叶子。命中后只需继续递归右子树，左子树（叶子）没有后代，省了一次无效递归。

12. 相同节点值的最大路径长度（687. Longest Univalue Path）

private int path = 0;

public int longestUnivaluePath(TreeNode root) {
    dfs(root);
    return path;
}

private int dfs(TreeNode root){
    if (root == null) return 0;
    int left = dfs(root.left);
    int right = dfs(root.right);
    int leftPath = root.left != null && root.left.val == root.val ? left + 1 : 0;
    int rightPath = root.right != null && root.right.val == root.val ? right + 1 : 0;
    path = Math.max(path, leftPath + rightPath);
    return Math.max(leftPath, rightPath);
}

再次使用“全局变量 + 向上返回”范式：子树返回“与当前节点值相同的最大单边延伸长度”（值不同则截断为 0），leftPath + rightPath 即为过当前节点的最长同值路径。

13. 间隔遍历（337. House Robber III）

     3
    / \
   2   3
    \   \
     3   1
Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

Map<TreeNode, Integer> cache = new HashMap<>();

public int rob(TreeNode root) {
    if (root == null) return 0;
    if (cache.containsKey(root)) return cache.get(root);
    int val1 = root.val;
    if (root.left != null) val1 += rob(root.left.left) + rob(root.left.right);
    if (root.right != null) val1 += rob(root.right.left) + rob(root.right.right);
    int val2 = rob(root.left) + rob(root.right);
    int res = Math.max(val1, val2);
    cache.put(root, res);
    return res;
}

树形动态规划：每个节点只有“抢（val1）”与“不抢（val2）”两种状态，取较大者。抢当前节点则孙子节点全部可抢；不抢则左右子节点均可考虑。由于不同路径会重复计算同一子树（例如 root.left 在多个分支中都会被求值），原文档用 Map<TreeNode, Integer> 做记忆化缓存，把指数级复杂度降到 O(n)。若不用缓存也可以改为“每个节点同时返回抢/不抢两个值”的状态压缩写法。

14. 找出二叉树中第二小的节点（671. Second Minimum Node In a Binary Tree）

Input:
   2
  / \
 2   5
    / \
    5  7

Output: 5

题目特殊性质：一个节点要么具有 0 个或 2 个子节点，如果有子节点，那么根节点是最小的节点。利用该性质，第二小的值必然来自某个“子节点值大于父节点值”的节点：

public int findSecondMinimumValue(TreeNode root) {
    if (root == null) return -1;
    if (root.left == null && root.right == null) return -1;
    int leftVal = root.left.val;
    int rightVal = root.right.val;
    if (leftVal == root.val) leftVal = findSecondMinimumValue(root.left);
    if (rightVal == root.val) rightVal = findSecondMinimumValue(root.right);
    if (leftVal != -1 && rightVal != -1) return Math.min(leftVal, rightVal);
    if (leftVal != -1) return leftVal;
    return rightVal;
}

子节点值等于当前值说明它不是“第二小”的候选，需要继续向该子树深处递归寻找；一旦子节点值大于当前值，它就是候选答案，无需再深入。

二、层次遍历：BFS 的层控技巧

原文档在层次遍历部分给出一个重要结论：

使用 BFS 进行层次遍历。不需要使用两个队列来分别存储当前层的节点和下一层的节点，因为在开始遍历一层的节点时，当前队列中的节点数就是当前层的节点数，只要控制遍历这么多节点数，就能保证这次遍历的都是当前层的节点。

这个“层入口时取一次 queue.size() 作为本层计数”的技巧，是层次遍历的标准写法。

1. 一棵树每层节点的平均数（637. Average of Levels in Binary Tree）

public List<Double> averageOfLevels(TreeNode root) {
    List<Double> ret = new ArrayList<>();
    if (root == null) return ret;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        int cnt = queue.size();
        double sum = 0;
        for (int i = 0; i < cnt; i++) {
            TreeNode node = queue.poll();
            sum += node.val;
            if (node.left != null) queue.add(node.left);
            if (node.right != null) queue.add(node.right);
        }
        ret.add(sum / cnt);
    }
    return ret;
}

循环内先固化 cnt，随后弹出的恰好是当前层的全部节点；子节点入队后在下一轮外层循环中被处理，层次界限由队列长度天然分隔。

2. 得到左下角的节点（513. Find Bottom Left Tree Value）

public int findBottomLeftValue(TreeNode root) {
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        root = queue.poll();
        if (root.right != null) queue.add(root.right);
        if (root.left != null) queue.add(root.left);
    }
    return root.val;
}

一个巧妙之处：先入右子节点、后入左子节点。BFS 按层从左到右出队，每层最后一个出队的节点就是该层最左的节点；当队列为空时，最后出队的 root 就是最后一层（最底层）的最左节点。全程只保留一个引用，无需记录层号。层次遍历打印的多行版本可对照 32.2 把二叉树打印成多行、32.3 按之字形顺序打印二叉树。

三、前中后序遍历：定义与非递归实现

以这棵小树为基准，四种遍历顺序为：

层次遍历顺序：[1 2 3 4 5 6]
前序遍历顺序：[1 2 4 5 3 6]
中序遍历顺序：[4 2 5 1 3 6]
后序遍历顺序：[4 5 2 6 3 1]

层次遍历使用 BFS 实现，利用的就是 BFS 一层一层遍历的特性；而前序、中序、后序遍历利用了 DFS 实现。前序、中序、后序遍历只是在对节点访问的顺序有一点不同，其它都相同：

// ① 前序：根 -> 左 -> 右
void dfs(TreeNode root) {
    visit(root);
    dfs(root.left);
    dfs(root.right);
}

// ② 中序：左 -> 根 -> 右
void dfs(TreeNode root) {
    dfs(root.left);
    visit(root);
    dfs(root.right);
}

// ③ 后序：左 -> 右 -> 根
void dfs(TreeNode root) {
    dfs(root.left);
    dfs(root.right);
    visit(root);
}

非递归实现的核心是用栈模拟系统调用栈，难点在于“何时该回头访问父节点”。下面三道题分别给出三种遍历的迭代写法。

1. 非递归实现二叉树的前序遍历（144. Binary Tree Preorder Traversal）

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> ret = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        if (node == null) continue;
        ret.add(node.val);
        stack.push(node.right);  // 先右后左，保证左子树先遍历
        stack.push(node.left);
    }
    return ret;
}

关键点：栈是后进先出的，所以先压右、再压左，左子树就会先被弹出遍历。允许压入 null 节点并靠 continue 跳过，省去了分支判空。

2. 非递归实现二叉树的后序遍历（145. Binary Tree Postorder Traversal）

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> ret = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        if (node == null) continue;
        ret.add(node.val);
        stack.push(node.left);
        stack.push(node.right);
    }
    Collections.reverse(ret);
    return ret;
}

原文档指出了这道题的巧思：前序遍历为 root -> left -> right，后序遍历为 left -> right -> root。把前序的访问顺序改成 root -> right -> left（即代码中先压左、后压右，先访问根），得到的序列恰好是后序遍历的逆序，最后 Collections.reverse 一次即得答案。这比标准写法（需要记录上一个访问节点来判断右子树是否已完成）简洁得多。

3. 非递归实现二叉树的中序遍历（94. Binary Tree Inorder Traversal）

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> ret = new ArrayList<>();
    if (root == null) return ret;
    Stack<TreeNode> stack = new Stack<>();
    TreeNode cur = root;
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
        TreeNode node = stack.pop();
        ret.add(node.val);
        cur = node.right;
    }
    return ret;
}

中序的迭代无法套用“全压栈”技巧，需要显式维护指针 cur：一路向左把路径上的节点全部入栈（它们是“左子树还没处理完”的待回头节点）；到最左后弹出访问，再转入该节点的右子树重复上述过程。外层 while 的条件 cur != null || !stack.isEmpty() 保证“还有右子树要走”或“还有路径节点要回头”时循环继续，这也是 BST 中序有序遍历（见下一节多题）的基础。

四、BST 专题：善用“中序有序”这一性质

原文档给出 BST 的两条基本定义：

二叉查找树（BST）：根节点大于等于左子树所有节点，小于等于右子树所有节点。二叉查找树中序遍历有序。

几乎所有 BST 题目都建立在第二条性质之上：中序遍历（或等价的“从右到左的反中序”）访问序列是单调有序的，有序后即可使用双指针、前驱比较等数组技巧。

1. 修剪二叉查找树（669. Trim a Binary Search Tree）

Input:

    3
   / \
  0   4
   \
    2
   /
  1

  L = 1
  R = 3

Output:

      3
     /
   2
  /
 1

题目描述：只保留值在 L ~ R 之间的节点：

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

BST 的有序性让裁剪变成剪枝决策：当前节点值大于 R 时，它及整个右子树都越界，只需返回左子树的修剪结果；小于 L 则反之。节点值在区间内时保留节点并分别修剪左右子树。

2. 寻找二叉查找树的第 k 个元素（230. Kth Smallest Element in a BST）

原文档给出了两种解法。中序遍历解法（找到第 k 个即停，平均提前终止）：

private int cnt = 0;
private int val;

public int kthSmallest(TreeNode root, int k) {
    inOrder(root, k);
    return val;
}

private void inOrder(TreeNode node, int k) {
    if (node == null) return;
    inOrder(node.left, k);
    cnt++;
    if (cnt == k) {
        val = node.val;
        return;
    }
    inOrder(node.right, k);
}

递归计数解法（按左右子树节点数定位 k 落在哪一侧）：

public int kthSmallest(TreeNode root, int k) {
    int leftCnt = count(root.left);
    if (leftCnt == k - 1) return root.val;
    if (leftCnt > k - 1) return kthSmallest(root.left, k);
    return kthSmallest(root.right, k - leftCnt - 1);
}

private int count(TreeNode node) {
    if (node == null) return 0;
    return 1 + count(node.left) + count(node.right);
}

第二种解法利用“左子树全部小于根”的性质：左子树节点数等于 k-1 时根就是答案；多于 k-1 时答案在左子树；少于时答案在右子树且 k 要减去 leftCnt + 1。若树中每个节点额外维护子树大小（如平衡树实现），可做到 O(log n)。该题对应剑指 Offer 的 54. 二叉查找树的第 K 个结点。

3. 把二叉查找树每个节点的值都加上比它大的节点之和（Convert BST to Greater Tree）

Input: The root of a Binary Search Tree like this:

              5
            /   \
           2     13

Output: The root of a Greater Tree like this:

             18
            /   \
          20     13

原文档提示：先遍历右子树。这正是“反向中序遍历”（右 -> 根 -> 左），访问序列单调递减，用一个累加器即可：

private int sum = 0;

public TreeNode convertBST(TreeNode root) {
    traver(root);
    return root;
}

private void traver(TreeNode node) {
    if (node == null) return;
    traver(node.right);
    sum += node.val;
    node.val = sum;
    traver(node.left);
}

以示例验证：先访问 13（sum=13），再访问 5（sum=18，5 改写为 18），最后访问 2（sum=20，2 改写为 20），与输出完全一致。

4. 二叉查找树的最近公共祖先（235. Lowest Common Ancestor of a Binary Search Tree）

        _______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.

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

BST 的有序性让 LCA 变成二分决策：p、q 都比当前节点小，则都在左子树，向左走；都比当前节点大则向右走；否则当前节点就是分叉点（一个在左、一个在右，或其一就是当前节点）。迭代实现下每层只走一步，空间 O(1)。

5. 二叉树的最近公共祖先（236. Lowest Common Ancestor of a Binary Tree）

       _______3______
      /              \
  ___5__           ___1__
 /      \         /      \
6        2       0        8
        /  \
       7    4

For 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.

换成普通二叉树后无法比较数值大小，改用“后序回溯”：

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);
    return left == null ? right : right == null ? left : root;
}

子树返回值的含义是“该子树中找到的 p/q 之一”：左右都非空说明 p、q 分居两侧，当前节点即 LCA；只有一侧非空则把该结果向上抛；命中 p 或 q 本身直接返回，天然覆盖“节点可以是自己的后代”的定义。BST 版与普通树的差异正体现了有序性对算法形态的影响。

6. 从有序数组中构造二叉查找树（108. Convert Sorted Array to Binary Search Tree）

public TreeNode sortedArrayToBST(int[] nums) {
    return toBST(nums, 0, nums.length - 1);
}

private TreeNode toBST(int[] nums, int sIdx, int eIdx){
    if (sIdx > eIdx) return null;
    int mIdx = (sIdx + eIdx) / 2;
    TreeNode root = new TreeNode(nums[mIdx]);
    root.left =  toBST(nums, sIdx, mIdx - 1);
    root.right = toBST(nums, mIdx + 1, eIdx);
    return root;
}

数组支持随机访问，直接二分：取区间中点作根，左半区间递归建左子树、右半区间建右子树，天然得到高度平衡的 BST。数组中点划分与 BST“根大于左、小于右”的定义严格对应。

7. 根据有序链表构造平衡的二叉查找树（109. Convert Sorted List to Binary Search Tree）

Given the sorted linked list: [-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

链表不能随机访问，原文档的做法是快慢指针找中点的前驱，先断链再递归：

public TreeNode sortedListToBST(ListNode head) {
    if (head == null) return null;
    if (head.next == null) return new TreeNode(head.val);
    ListNode preMid = preMid(head);
    ListNode mid = preMid.next;
    preMid.next = null;  // 断开链表
    TreeNode t = new TreeNode(mid.val);
    t.left = sortedListToBST(head);
    t.right = sortedListToBST(mid.next);
    return t;
}

private ListNode preMid(ListNode head) {
    ListNode slow = head, fast = head.next;
    ListNode pre = head;
    while (fast != null && fast.next != null) {
        pre = slow;
        slow = slow.next;
        fast = fast.next.next;
    }
    return pre;
}

preMid 让 fast 从 head.next 起步，使得 slow 停在中点的前一个节点，preMid.next 即中点；断开 preMid.next 使左右两段子链表各自独立，避免递归边界纠缠。相比第 6 题，多出的正是“链表如何二分”这一难点。

8. 在二叉查找树中寻找两个节点，使它们的和为一个给定值（653. Two Sum IV - Input is a BST）

Input:

    5
   / \
  3   6
 / \   \
2   4   7

Target = 9

Output: True

原文档强调：

使用中序遍历得到有序数组之后，再利用双指针对数组进行查找。应该注意到，这一题不能用分别在左右子树两部分来处理这种思想，因为两个待求的节点可能分别在左右子树中。

public boolean findTarget(TreeNode root, int k) {
    List<Integer> nums = new ArrayList<>();
    inOrder(root, nums);
    int i = 0, j = nums.size() - 1;
    while (i < j) {
        int sum = nums.get(i) + nums.get(j);
        if (sum == k) return true;
        if (sum < k) i++;
        else j--;
    }
    return false;
}

private void inOrder(TreeNode root, List<Integer> nums) {
    if (root == null) return;
    inOrder(root.left, nums);
    nums.add(root.val);
    inOrder(root.right, nums);
}

“树形问题不能总是分治到子树”是本题最有价值的经验教训：两个和为 k 的节点可能一个在左子树、一个在右子树，跨子树的信息只有在序列化为有序数组后才能被双指针处理。

9. 在二叉查找树中查找两个节点之差的最小绝对值（530. Minimum Absolute Difference in BST）

Input:

   1
    \
     3
    /
   2

Output:

1

利用二叉查找树的中序遍历为有序的性质，计算中序遍历中临近的两个节点之差的绝对值，取最小值（有序序列的最小差必然出现在相邻元素之间）：

private int minDiff = Integer.MAX_VALUE;
private TreeNode preNode = null;

public int getMinimumDifference(TreeNode root) {
    inOrder(root);
    return minDiff;
}

private void inOrder(TreeNode node) {
    if (node == null) return;
    inOrder(node.left);
    if (preNode != null) minDiff = Math.min(minDiff, node.val - preNode.val);
    preNode = node;
    inOrder(node.right);
}

与上一题不同，本题无需物化整个数组，用一个 preNode 记录中序前驱即可流式比较，空间上只消耗递归栈深度。

10. 寻找二叉查找树中出现次数最多的值（501. Find Mode in Binary Search Tree）

   1
    \
     2
    /
   2

return [2].

答案可能不止一个，也就是有多个值出现的次数一样多。BST 的中序遍历把相同值聚成连续段，只需统计连续段的长度：

private int curCnt = 1;
private int maxCnt = 1;
private TreeNode preNode = null;

public int[] findMode(TreeNode root) {
    List<Integer> maxCntNums = new ArrayList<>();
    inOrder(root, maxCntNums);
    int[] ret = new int[maxCntNums.size()];
    int idx = 0;
    for (int num : maxCntNums) {
        ret[idx++] = num;
    }
    return ret;
}

private void inOrder(TreeNode node, List<Integer> nums) {
    if (node == null) return;
    inOrder(node.left, nums);
    if (preNode != null) {
        if (preNode.val == node.val) curCnt++;
        else curCnt = 1;
    }
    if (curCnt > maxCnt) {
        maxCnt = curCnt;
        nums.clear();
        nums.add(node.val);
    } else if (curCnt == maxCnt) {
        nums.add(node.val);
    }
    preNode = node;
    inOrder(node.right, nums);
}

注意两个细节：curCnt 初值为 1（首个节点自成一段）；当 curCnt == maxCnt 时直接追加而非清栈，保证并列最多的值都被保留。由于 BST 允许重复值（原文档定义使用“大于等于/小于等于”），不能用“值严格递增”来断言唯一性。

五、Trie：前缀树/字典树

Trie，又称前缀树或字典树，用于判断字符串是否存在或者是否具有某种字符串前缀。Trie 把字符串集合的公共前缀压缩为共享路径：插入与检索的成本取决于字符串长度 m 而非集合大小 n，这正是它优于逐字符串哈希检索的地方。

1. 实现一个 Trie（208. Implement Trie (Prefix Tree)）

class Trie {

    private class Node {
        Node[] childs = new Node[26];
        boolean isLeaf;
    }

    private Node root = new Node();

    public Trie() {
    }

    public void insert(String word) {
        insert(word, root);
    }

    private void insert(String word, Node node) {
        if (node == null) return;
        if (word.length() == 0) {
            node.isLeaf = true;
            return;
        }
        int index = indexForChar(word.charAt(0));
        if (node.childs[index] == null) {
            node.childs[index] = new Node();
        }
        insert(word.substring(1), node.childs[index]);
    }

    public boolean search(String word) {
        return search(word, root);
    }

    private boolean search(String word, Node node) {
        if (node == null) return false;
        if (word.length() == 0) return node.isLeaf;
        int index = indexForChar(word.charAt(0));
        return search(word.substring(1), node.childs[index]);
    }

    public boolean startsWith(String prefix) {
        return startWith(prefix, root);
    }

    private boolean startWith(String prefix, Node node) {
        if (node == null) return false;
        if (prefix.length() == 0) return true;
        int index = indexForChar(prefix.charAt(0));
        return startWith(prefix.substring(1), node.childs[index]);
    }

    private int indexForChar(char c) {
        return c - 'a';
    }
}

三个方法的区别值得对照理解：

insert：路径走完时把节点标记 isLeaf = true，表示“以这里结尾的串是一个完整单词”；
search：路径走完时必须检查 isLeaf，否则 "app" 存在而 "ap" 只被当作前缀时会误判；
startsWith：路径走完即返回 true，不需要 isLeaf——前缀查询只要求路径存在。

节点用长度为 26 的数组按 c - 'a' 索引，字符集固定为小写字母，因此每节点空间开销为 O(26)。若字符集更大，可把数组换成 Map。search 中 node == null 返回 false 覆盖了“走到中途路径断开”的情况，与“走完全程但不是单词”由 isLeaf 兜底，二者缺一不可。

2. 实现一个 Trie，用来求前缀和（677. Map Sum Pairs）

Input: insert("apple", 3), Output: Null
Input: sum("ap"), Output: 3
Input: insert("app", 2), Output: Null
Input: sum("ap"), Output: 5

class MapSum {

    private class Node {
        Node[] child = new Node[26];
        int value;
    }

    private Node root = new Node();

    public MapSum() {

    }

    public void insert(String key, int val) {
        insert(key, root, val);
    }

    private void insert(String key, Node node, int val) {
        if (node == null) return;
        if (key.length() == 0) {
            node.value = val;
            return;
        }
        int index = indexForChar(key.charAt(0));
        if (node.child[index] == null) {
            node.child[index] = new Node();
        }
        insert(key.substring(1), node.child[index], val);
    }

    public int sum(String prefix) {
        return sum(prefix, root);
    }

    private int sum(String prefix, Node node) {
        if (node == null) return 0;
        if (prefix.length() != 0) {
            int index = indexForChar(prefix.charAt(0));
            return sum(prefix.substring(1), node.child[index]);
        }
        int sum = node.value;
        for (Node child : node.child) {
            sum += sum(prefix, child);
        }
        return sum;
    }

    private int indexForChar(char c) {
        return c - 'a';
    }
}

与第 1 题的结构化差异在于：每个节点带 value 字段存“以该节点为结尾的 key 的权重”，重复 insert 直接覆盖旧值。sum(prefix) 先沿前缀走到底，再对该子树做一次全量 DFS 累加所有 value。以示例验证：insert("apple", 3) 后 sum("ap") 进入 p 节点子树累加得 3；再 insert("app", 2) 后 p 节点子树里多了一个 value=2 的端点，sum("ap") 变为 5，与题目输出一致。若查询远多于更新，也可在节点上维护子树权重和，把每次求和降为 O(m)——这属于原文档实现之外的常见优化方向。

六、题单速查与延伸阅读

汇总本文全部 31 道题的题号与所属模式，便于按考点检索：

板块	题号与题名	核心模式
递归	104 树的高度	后序递归返回高度
递归	110 平衡树	一次递归算高度 + 全局判定
递归	543 两节点的最长路径	返回高度 + 全局记录直径
递归	226 翻转树	交换左右子树，注意先存指针
递归	617 归并两棵树	双边判空 + 值相加
递归	112 判断路径和	向下递减目标值
递归	437 路径和计数	双递归：枚举起点 + 固定起点统计
递归	572 子树	双递归：匹配 + 枚举起点
递归	101 树的对称	双指针镜像递归
递归	111 最小路径	处理单侧为空的叶子判定
递归	404 左叶子之和	叶子判定 + 剪枝
递归	687 相同值最长路径	返回单边长度 + 全局路径
递归	337 间隔遍历	树形 DP + 记忆化缓存
递归	671 第二小节点	利用题目特殊性质递归下探
层次遍历	637 每层平均数	层入口取 size 控制层界
层次遍历	513 左下角节点	先右后左入队，末次出队即答案
遍历	144/145/94 前中后序非递归	栈模拟调用栈；后序用逆序技巧
BST	669 修剪 BST	越界剪枝
BST	230 第 k 个元素	中序计数 / 子树规模定位
BST	转换 Greater Tree	反向中序 + 累加器
BST	235/236 最近公共祖先	有序二分决策 / 后序回溯
BST	108/109 有序数组链表建 BST	中点分治；链表快慢指针找中点
BST	653 BST 两数之和	中序数组 + 双指针
BST	530 最小绝对差	中序前驱流式比较
BST	501 众数	中序连续段统计
Trie	208 实现 Trie	Node 数组 + isLeaf 区分单词与前缀
Trie	677 Map Sum Pairs	节点 value + 前缀子树求和

树形结构的递归题解还可以继续结合 CS-Notes 仓库内的其他专题深入：

剑指 Offer 题解与剑指 Offer 题解 - 目录：其中“树”板块收录了 7. 重建二叉树（前中序互推建树）、36. 二叉搜索树与双向链表、55.1 二叉树的深度、55.2 平衡二叉树、68. 树中两个节点的最低公共祖先等与本文强对应的面试原题；
Leetcode 题解 - 目录：Leetcode 系列的完整索引，本文属于其“数据结构相关”板块，可与 Leetcode 题解 - 栈和队列（栈正是非递归遍历的模拟工具）对照学习。

七、结语：树题的三层解题阶梯

回顾全文，树形结构题存在清晰的递进关系，可作为面试前的自检清单：

会写后序递归：能默写“空树基线 + 左右子树递归 + 组合”模板，并理解返回值语义（如高度）与全局状态（如直径、平衡标记）的分工——这是 14 道递归题的共同骨架；
会换遍历形态：BFS 层控技巧处理层相关问题，迭代 DFS 用栈模拟调用栈，并掌握“前序逆序得后序”的转换；
会用结构性质降维：BST 的一切便利来自中序有序，把树问题转化为有序数组上的双指针、前驱比较或段统计，是 BST 十道题的统一思路；Trie 则反过来利用“前缀共享”把字符串问题组织为树路径问题。

按这三层阶梯对照本文题单逐一实现与复盘，即可覆盖二叉树与 BST 面试题目中的绝大多数高频考点。

CS-Notes

:books: 技术面试必备基础知识、Leetcode、计算机操作系统、计算机网络、系统设计

项目地址：https://gitcode.com/GitHub_Trending/cs/CS-Notes

登录后查看全文