#105. 从前序与中序遍历序列构造二叉树

• LeetCode：105. 从前序与中序遍历序列构造二叉树
• 难度：中等
• 归类：二叉树、分治
• 主解法：前序找根，中序切分左右，递归构造

#先给结论

两种遍历提供的信息不同：

• 前序遍历顺序是「根 → 左子树 → 右子树」，所以当前子树的第一个前序元素一定是根节点。
• 中序遍历顺序是「左子树 → 根 → 右子树」，所以根节点在中序数组中的位置可以划分左右子树。

每一步的操作非常直接：

1. 从前序数组 shift 出第一个元素作为根。
2. 在中序数组中找到这个根的位置 index。
3. 用 index 把中序切成左、右两部分。
4. 因为根已经被 shift 掉，前序数组里紧接着的 index 个元素就是左子树的前序，后面剩下的是右子树的前序。
5. 递归构造左右子树。

#题目描述

给定两个整数数组 preorder 和 inorder：

• preorder 是同一棵二叉树的前序遍历。
• inorder 是同一棵二叉树的中序遍历。

请构造并返回这棵二叉树的根节点。

示例 1：

输入：
preorder = [3, 9, 20, 15, 7]
inorder  = [9, 3, 15, 20, 7]

输出：[3, 9, 20, null, null, 15, 7]

对应的树：

      3
     / \
    9  20
      /  \
     15   7

示例 2：

输入：preorder = [-1], inorder = [-1]
输出：[-1]

题目保证：

• 1 <= preorder.length <= 3000。
• inorder.length === preorder.length。
• 节点值互不相同。
• 两个数组都是同一棵二叉树的合法遍历结果。

值互不相同非常关键：它保证每个根节点在中序数组中只有一个位置，前序和中序遍历可以唯一确定二叉树。

#问题本质

对于任意一棵非空子树：

1. 前序数组的第一个元素是根节点。
2. 在中序数组中找到根节点。
3. 根节点左侧属于左子树，右侧属于右子树。
4. 左子树有多少个节点，前序数组里根后面就跟着多少个左子树节点；再往后是右子树节点。
5. 把前序和中序分别切成左右两份，递归构造即可。

核心就一句话：前序取根，中序定界，按节点数切分。

#子数组切分逻辑

这段代码的优雅之处在于直接传子数组，不需要维护下标区间。理解切分规则是关键。

假设当前递归收到：

preorder = [3, 9, 20, 15, 7]
inorder  = [9, 3, 15, 20, 7]

#第一步：取根

const mid = preorder.shift()   // mid = 3，preorder 变成 [9, 20, 15, 7]

#第二步：找根在中序中的位置

const index = inorder.indexOf(mid)   // index = 1

index 同时表示左子树的节点数（中序里根左边有 1 个节点）。

#第三步：切分中序

inorder.slice(0, index)      // [9]      → 左子树中序
inorder.slice(index + 1)     // [15, 20, 7] → 右子树中序（跳过根）

#第四步：切分前序

这里有一个细节：因为根已经被 shift 掉了，此时 preorder 已经是 [9, 20, 15, 7]。

前序遍历的结构是「根 → 左子树 → 右子树」。根没了，剩下的就是「左子树 → 右子树」。而左子树恰好有 index 个节点，所以：

preorder.slice(0, index)     // [9]      → 左子树前序（前 index 个）
preorder.slice(index)        // [20, 15, 7] → 右子树前序（剩余全部）

注意右子树前序用的是 slice(index) 而不是 slice(index + 1)，因为根已经在 shift 时被移除了。

#为什么 index 能同时切分两个数组？

index 的本质不是"下标"，而是左子树的节点个数。

• 在中序数组里，index 表示根左边有 index 个元素，这些元素构成左子树。
• 在前序数组里（根已被 shift 掉），剩下的就是「左子树前序 → 右子树前序」。而一棵子树有多少个节点，与遍历方式无关，所以左子树在前序里同样占 index 个节点。

以示例数据对照：

preorder = [3, 9, 20, 15, 7]   // 前序：根 3，然后左子树，然后右子树
inorder  = [9, 3, 15, 20, 7]   // 中序：左子树，根 3，然后右子树

取根 3 后，index = 1。左子树都只有 1 个节点（9），右子树都有 3 个节点（15, 20, 7）：

两者对应的节点集合完全相同，只是排列顺序不同（前序是根左右，中序是左右根）。因此同一个 index 既能切中序，也能切前序。

#切分对照

#示例推演

输入：

preorder = [3, 9, 20, 15, 7]
inorder  = [9, 3, 15, 20, 7]

第一次递归：

• mid = 3，preorder 变为 [9, 20, 15, 7]
• index = 1
• 左子树：buildTree([9], [9])
• 右子树：buildTree([20, 15, 7], [15, 20, 7])

构造左子树：

• mid = 9，preorder 变为 []
• index = 0
• 左右子树都是空数组，返回 null
• 得到叶子节点 9

构造右子树：

• mid = 20，preorder 变为 [15, 7]
• index = 1
• 左子树：buildTree([15], [15]) → 叶子节点 15
• 右子树：buildTree([7], [7]) → 叶子节点 7
• 得到子树 20，左右分别是 15、7

最终得到：

      3
     / \
    9  20
      /  \
     15   7

#代码实现

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = val === undefined ? 0 : val;
 *     this.left = left === undefined ? null : left;
 *     this.right = right === undefined ? null : right;
 * }
 */

/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
var buildTree = function (preorder, inorder) {
    // 任一遍历序列为空，说明当前子树没有节点
    if (!preorder.length || !inorder.length) {
        return null;
    }

    // 前序遍历的第一个节点就是当前子树的根节点
    const mid = preorder.shift();
    const root = new TreeNode(mid);

    // 根在中序遍历中的下标，也等于左子树的节点数量
    const index = inorder.indexOf(mid);

    // 根已从 preorder 中移除，前 index 个节点属于左子树
    root.left = buildTree(preorder.slice(0, index), inorder.slice(0, index));

    // 前序从 index 开始是右子树；中序从 index + 1 开始以跳过根节点
    root.right = buildTree(preorder.slice(index), inorder.slice(index + 1));

    // 返回已经连接好左右子树的根节点
    return root;
};

#代码与思路对照

#正确性说明

可以对当前子树的节点数进行归纳证明。

#基础情况

当 preorder 或 inorder 为空时，当前子树没有节点，返回 null，结果正确。

#归纳步骤

假设节点数少于当前子树的区间都能被正确构造。

对于当前非空区间：

1. 根据前序遍历定义，preorder 的第一个元素一定是当前子树的根节点。
2. 根节点在中序数组左侧的所有节点一定属于左子树，右侧的所有节点一定属于右子树。
3. index 等于左子树节点数，因此前序数组中（shift 掉根后）的前 index 个元素恰好属于左子树，剩余元素属于右子树。
4. 两个递归调用处理的节点数都少于当前子树。根据归纳假设，它们会正确构造左右子树。

将两棵子树连接到当前根节点后，当前子树也被正确构造。因此算法能构造出完整二叉树。

#边界与陷阱

• 空数组： 官方约束至少有一个节点，但当前实现也会正确返回 null。
• 单节点： 左右子树切分后都是空数组，直接返回一个叶子节点。
• 完全偏斜的树： 递归深度可能达到 n。
• 节点值重复： 当前算法依赖「值 → 唯一下标」；题目已保证值互不相同。
• 前序右子树为什么是 slice(index)： 因为 shift() 已经移除了根，前序数组里剩下的就是「左子树 → 右子树」拼接而成，左子树占 index 个，所以右子树从 index 开始切。
• 中序右子树为什么是 slice(index + 1)： 中序数组需要跳过根节点本身。
• 复杂度敏感场景： shift()、indexOf()、slice() 都会创建或移动数组元素。对于超大规模数据（如 n > 10^5），建议使用下标区间版本来避免额外开销。

#复杂度分析

设当前递归层处理的节点数为 n。

• preorder.shift()：O(n)，需要移动数组后续元素。
• inorder.indexOf(mid)：O(n)，线性查找。
• slice：O(k)，k 为切片长度。

一层递归的总工作量是 O(n)。递归深度取决于树的形状：

• 平衡树： 深度为 O(log n)，总时间复杂度为 O(n log n)。
• 偏斜树： 深度为 O(n)，总时间复杂度退化为 O(n²)。

对于本题 n <= 3000，该实现完全可以通过。

额外空间：

• 每次 slice 都会创建新数组，递归过程中同时存在的数组总量为 O(n)。
• 递归栈深度为 O(h)，最坏 O(n)。

返回的二叉树本身属于题目要求的输出，不计入额外空间。

#面试官递进追问

#1. 为什么前序与中序遍历能唯一确定这棵树？

前序遍历确定每棵子树的根节点，中序遍历确定根节点左右两侧分别属于哪棵子树。节点值互不相同时，这个划分在每层都唯一，因此整棵树唯一。

#2. 为什么前序数组可以用 shift() 取根？

前序遍历的定义就是先访问根节点。当前递归收到的 preorder 子数组，第一个元素一定是该子树的根。

#3. 右子树的前序为什么是 preorder.slice(index) 而不是 slice(index + 1)？

因为 shift() 已经把根从 preorder 中移除了。此时前序数组的结构是「左子树前序 → 右子树前序」，左子树占 index 个节点，所以右子树从 index 开始。

#4. 如果不用 shift()，右子树的前序该怎么切？

如果不修改原数组，前序结构是「根 → 左子树前序 → 右子树前序」。那么左子树前序是 slice(1, 1 + index)，右子树前序是 slice(1 + index)。

#5. indexOf 每层都是 O(n)，有没有更快的办法？

可以预先建立一个「值 → 中序下标」的哈希表，把查找降到平均 O(1)。如果配合传递下标区间而不是 slice 子数组，还能避免数组拷贝，整体优化到 O(n) 时间、O(h) 递归栈空间。

#6. 为什么题目需要保证节点值互不相同？

如果存在重复值，单个值无法唯一对应中序数组中的一个位置，前序和中序遍历也不一定能唯一确定树；简单的「值 → 下标」映射会失效。

#7. 最坏情况下递归深度是多少？

完全左偏或完全右偏时，每次递归只减少一个节点，递归深度为 O(n)；平衡树的递归深度则为 O(log n)。

#8. 这段代码的时间复杂度在什么情况下会退化成 O(n²)？

当树完全偏斜时，每层都要对长度为 O(n) 的数组执行 shift、indexOf 和 slice，总共 n 层，所以是 O(n²)。

#常见错误

• 误以为前序右子树是 preorder.slice(index + 1)，忘了根已经被 shift 掉了。
• 中序右子树写成 inorder.slice(index)，没有跳过根节点。
• 用 preorder[0] 取根后没有 shift，导致前序切分时下标错位。
• 忽视节点值重复会破坏唯一性。
• 对超大规模数据使用此实现，导致时间和空间开销过大。

#可迁移总结

• 前序 + 中序： 前序找根，中序分左右。
• 后序 + 中序： 后序找根（最后一个元素），中序分左右，切分方式类似。
• 前序 + 后序： 一般不能唯一确定任意二叉树，因为缺少明确的左右边界。
• 一句话记忆： 前序 shift 取根，中序 indexOf 定位，按左子树节点数切分两边。

#刷题后自测

先只回答第 1 题，再展开后续问题：

1. 为什么前序右子树用 slice(index)，而中序右子树用 slice(index + 1)？