Hot 100 --- 从前序与中序遍历序列构造二叉树

本文概览：本文以LeetCode题目"从前序与中序遍历序列构造二叉树"为例，详细讲解如何把"分治构造"的想法转化为递归代码，重点说明递归的出口和参数传递

一、题目

从前序与中序遍历序列构造二叉树题目

二、题目分析

这题的难点不是思路本身——给你前序和中序序列，手动画出一棵二叉树大多数人都会。真正的难点是把这套手动操作的过程精确地转化成代码。手动操作时，每一步"找根节点、切左右子树"都很自然，但写代码时你必须回答：递归的出口是什么？每一轮要传哪些参数？子树的范围怎么从上一轮推导出来？只要有一个环节模糊，代码就写不出来

思路概览

Java 实现代码如下

public TreeNode buildTree(int[] preorder, int[] inorder) {
    if(preorder.length == 0 || inorder.length == 0) {
        return null;
    }
    // 构建映射表,记录中序遍历中每个节点的索引,方便后续快速定位
    Map<Integer, Integer> inMap = new HashMap<>();
    for(int i = 0; i < inorder.length; i++) {
        inMap.put(inorder[i], i);
    }
    // 递归构建树
    return helper(preorder, 0, preorder.length-1,
                       inorder, 0, inorder.length-1,
                       inMap);
}

private TreeNode helper(int[] preorder, int preStart, int preEnd,
                        int[] inorder, int inStart, int inEnd,
                        Map<Integer, Integer> inMap)
{
    // 递归终止条件,说明没有节点了
    if(preStart > preEnd || inStart > inEnd) {
        return null;
    }
    // 构建根节点
    TreeNode root = new TreeNode(preorder[preStart]);
    // 从中序遍历的索引表中定位到根节点的索引
    int inRoot = inMap.get(root.val);
    // 计算左子树的节点数量
    int leftSize = inRoot - inStart;
    // 递归构建左子树
    root.left = helper(preorder, preStart+1, preStart+leftSize,
                        inorder, inStart, inRoot-1,
                        inMap);
    // 递归构建右子树
    root.right = helper(preorder, preStart+leftSize+1, preEnd,
                         inorder, inRoot+1, inEnd,
                         inMap);
    return root;
}

思路简要说明

核心是分治：每轮从前序序列中取出根节点，再从中序序列中找到根的位置把左右子树分开，然后对左右子树分别递归做同样的事

每轮的操作：取前序第一个值作为根 → 在中序中定位根 → 根左边是左子树，根右边是右子树 → 用左子树节点数在前序中切出左右子树的序列 → 递归
递归出口：当前范围为空（preStart > preEnd 或 inStart > inEnd），说明没有节点了
递归参数：前序数组 + 前序起止索引 + 中序数组 + 中序起止索引，共 6 个范围参数
优化：用哈希表 inMap 记录中序遍历值到索引的映射，把每次查找从 O(n) 降到 O(1)

三、思路详解

构建过程的完整推演

前序遍历的结构是 [根][左子树][右子树]，中序遍历的结构是 [左子树][根][右子树]。这两个结构就是构建的依据

用一个具体例子来推演整个过程：

1 2	前序遍历：[3, 9, 20, 15, 7] 中序遍历：[9, 3, 15, 20, 7]

第 1 轮：处理整棵树

前序序列 [3, 9, 20, 15, 7]，中序序列 [9, 3, 15, 20, 7]

① 前序第一个值是 3，所以根节点 = 3

② 在中序序列中找 3 的位置：[9, |3|, 15, 20, 7]，索引 = 1

③ 根据中序的结构 [左][根][右]，3 的左边 [9] 是左子树，3 的右边 [15, 20, 7] 是右子树。所以左子树有 1 个节点，右子树有 3 个节点

④ 根据前序的结构 [根][左][右]，根之后的前 1 个值是左子树，剩余的是右子树：

前序：[3]  [9]  [20, 15, 7]
      根    左     右

中序：[9]  [3]  [15, 20, 7]
      左    根     右

到此，根节点 3 构建好了，接下来要分别构建左子树 [9] 和右子树 [20,15,7]

第 2 轮：构建左子树（3 的左孩子）

前序左子树 [9]，中序左子树 [9]

① 前序第一个值是 9，所以这个子树的根节点 = 9

② 在中序中找 9：[|9|]，索引 = 0（相对当前范围）

③ 9 的左边为空，9 的右边为空 → 没有子树了

前序：[9]
      根

中序：[9]
      根

节点 9 是个叶子。3 的左孩子 = 9，左子树构建完毕

第 3 轮：构建右子树（3 的右孩子）

前序右子树 [20, 15, 7]，中序右子树 [15, 20, 7]

① 前序第一个值是 20，所以这个子树的根节点 = 20

② 在中序中找 20：[15, |20|, 7]，索引 = 1（相对当前范围）

③ 20 的左边 [15] 是左子树，20 的右边 [7] 是右子树。左子树有 1 个节点，右子树有 1 个节点

④ 前序中根之后前 1 个是左子树，剩余是右子树：

前序：[20]  [15]  [7]
       根     左    右

中序：[15]  [20]  [7]
       左     根    右

根节点 20 构建好了，继续构建它的左右子树

第 4 轮：构建 20 的左孩子

前序 [15]，中序 [15]

前序第一个值是 15，中序中 15 左右都为空 → 叶子节点。20 的左孩子 = 15

第 5 轮：构建 20 的右孩子

前序 [7]，中序 [7]

前序第一个值是 7，中序中 7 左右都为空 → 叶子节点。20 的右孩子 = 7

构建完成：

整个过程的关键：每一轮都能从上一轮的范围内确定"根节点是谁"和"左右子树各占多少"，然后把这个范围传给下一轮。这就是分治的核心——大问题拆成同结构的小问题

把思路变成递归

现在思路很清楚了，但怎么写成代码？让我们套用之前讲的"递归三步法"。

1. 找出口

**出口就是"没有节点可构造"**。当某个范围（前序范围或中序范围）为空时，说明这一轮没有节点，返回 null

1
2
3

if (preStart > preEnd || inStart > inEnd) {
    return null;
}

2. 找当前节点要做什么

构造根节点。根节点就是当前前序范围的第一项：

1	TreeNode root = new TreeNode(preorder[preStart]);

3. 找下一轮的参数

这是最关键的一步——下一轮要传什么参数，才能让子节点和当前节点做一样的事？

观察我们的思路：每轮要做的事是"给我前序的一段和中序的一段，我构造出这棵子树"。所以每轮都需要：

前序遍历数组 + 前序遍历的起止索引（preStart, preEnd）
中序遍历数组 + 中序遍历的起止索引（inStart, inEnd）

4. 怎么切出左右子树的范围

假设当前是这一轮：

前序：[..., preStart, ..., ..., preEnd]
                ↑ 根节点

中序：[..., inStart, ..., ..., inEnd]
                ↑ inRoot 根节点索引

我们已经在中序中找到 inRoot，接下来要算左子树的节点数：

1	int leftSize = inRoot - inStart;

左子树的参数：

前序：从 preStart+1 到 preStart+leftSize（根节点后面 leftSize 个就是左子树）
中序：从 inStart 到 inRoot-1（根节点左边就是左子树）

右子树的参数：

前序：从 preStart+leftSize+1 到 preEnd（左子树之后就是右子树）
中序：从 inRoot+1 到 inEnd（根节点右边就是右子树）

把这些代入递归调用即可：

root.left = helper(preorder, preStart+1, preStart+leftSize,
                    inorder, inStart, inRoot-1,
                    inMap);
root.right = helper(preorder, preStart+leftSize+1, preEnd,
                     inorder, inRoot+1, inEnd,
                     inMap);

用图来理解范围切分

把第一轮的所有范围画出来，方便看递归的传参：

前序遍历：[3, 9, 20, 15, 7]
索引：      0  1   2   3   4

中序遍历：[9, 3, 15, 20, 7]
索引：      0  1   2   3   4

哈希表 inMap：{9→0, 3→1, 15→2, 20→3, 7→4}

第一轮 helper(0, 4, 0, 4)：

前序范围：preStart=0, preEnd=4   →  [3, 9, 20, 15, 7]
中序范围：inStart=0, inEnd=4     →  [9, 3, 15, 20, 7]
              ↑ inStart       ↑ inEnd
                            ↑ inRoot=1（根节点3的索引）

根节点 = preorder[0] = 3
leftSize = inRoot - inStart = 1 - 0 = 1

切分：

前序左：[preStart+1, preStart+leftSize] = [1, 1]              → [9]
前序右：[preStart+leftSize+1, preEnd]   = [2, 4]              → [20,15,7]
中序左：[inStart, inRoot-1]              = [0, 0]              → [9]
中序右：[inRoot+1, inEnd]                = [2, 4]              → [15,20,7]

第二轮（构造节点 9）helper(1, 1, 0, 0)：

前序范围：preStart=1, preEnd=1   →  [9]
中序范围：inStart=0, inEnd=0     →  [9]
inRoot=0（左子树 9 的索引）

根节点 = preorder[1] = 9
leftSize = 0 - 0 = 0

切分：

1 2	前序左：[2, 1] → preStart > preEnd，出口，返回 null 前序右：[2, 1] → preStart > preEnd，出口，返回 null

节点 9 是个叶子

第三轮（构造节点 20）helper(2, 4, 2, 4)：

前序范围：preStart=2, preEnd=4   →  [20, 15, 7]
中序范围：inStart=2, inEnd=4     →  [15, 20, 7]
inRoot=3（节点20的索引）

根节点 = preorder[2] = 20
leftSize = 3 - 2 = 1

切分：

前序左：[3, 3]              → [15]
前序右：[4, 4]              → [7]
中序左：[2, 2]              → [15]
中序右：[4, 4]              → [7]

继续递归构造 15 和 7，都是叶子

构造完成：

优化：用哈希表加速中序遍历的查找

每轮递归都需要在中序遍历中找到根节点的索引。如果每次都在中序数组中线性查找，时间复杂度是 O(n)，n 个节点就要 O(n²) 总时间

优化方法：在调用 helper 之前，先用一次遍历构建哈希表 inMap，把每个节点的值映射到它在数组中的索引。这样每轮查找索引的时间就是 O(1)，总时间复杂度降到 O(n)

Map<Integer, Integer> inMap = new HashMap<>();
for (int i = 0; i < inorder.length; i++) {
    inMap.put(inorder[i], i);
}

后续查找时直接 inMap.get(root.val) 即可

复杂度分析

时间复杂度：O(n)，每个节点被处理一次，加上哈希表的 O(n) 初始化
空间复杂度：O(n)，哈希表 O(n) + 递归栈 O(h)，h 为树高，最坏 O(n)