跳转至

105. 从前序与中序遍历构造二叉树（Construct Binary Tree from Preorder and Inorder Traversal）

频次 ★★★★ · 难度 🟡 · 高频：字节/腾讯

题目

根据前序和中序遍历结果重建二叉树（树中无重复值）。

示例： 

前序: [3,9,20,15,7]
中序: [9,3,15,20,7]
输出: 二叉树 3 → 9 / 20 → 15 / 7

思路

分治递归：

  • 前序第一个元素是根节点
  • 在中序中找到根位置，左侧是左子树、右侧是右子树
  • 前序中紧跟根之后的「左子树长度」个元素是左子树的前序序列，再之后是右子树前序
  • 递归处理

优化：用 Map<值, 中序下标> 把根定位加速到 O(1)。

代码

private Map<Integer, Integer> inMap;  // 值 → 中序索引

public TreeNode buildTree(int[] preorder, int[] inorder) {
    inMap = new HashMap<>();
    for (int i = 0; i < inorder.length; i++) inMap.put(inorder[i], i);
    return build(preorder, 0, preorder.length - 1, 0);
}

// build 参数: 前序数组, 前序左边界, 前序右边界, 中序左边界
private TreeNode build(int[] pre, int preL, int preR, int inL) {
    if (preL > preR) return null;
    TreeNode root = new TreeNode(pre[preL]);
    int inIdx = inMap.get(root.val);       // 根在中序中的位置
    int leftSize = inIdx - inL;            // 左子树节点数
    root.left = build(pre, preL + 1, preL + leftSize, inL);
    root.right = build(pre, preL + leftSize + 1, preR, inIdx + 1);
    return root;
}

复杂度

  • 时间：O(n) —— HashMap 加速中序查找
  • 空间：O(n) —— HashMap + 递归栈

边界条件

  • 长度为 0：返回 null
  • 单节点：返回该节点
  • 左/右单支树：leftSize = 0 或 rightSize = 0

变式

参数形式的三种等价写法

信息量相同，任给 3 个下标就能推出第 4 个（不变量：preR - preL == inR - inL，两个窗口装同一批节点、长度必等）。

形式 参数 来源 说明
四参数 preStart, preEnd, inStart, inEnd walkccc.me 等主流参考实现 最易懂，边界全显式写出
三参数（len） preL, inL, len LeetCode Wiki（doocs 镜像官方题解） preEnd、inEnd 由 len 隐含
三参数（丢 inEnd） preL, preR, inL 本仓库 wiki 原版 inEnd = inL + (preR - preL)

四参数版（推荐，边界显式）：

private TreeNode build(int[] pre, int preStart, int preEnd,
                       int[] in,  int inStart,  int inEnd,
                       Map<Integer, Integer> inToIndex) {
    if (preStart > preEnd) return null;
    int rootVal = pre[preStart];
    int rootInIndex = inToIndex.get(rootVal);
    int leftSize = rootInIndex - inStart;            // ★ 左子树节点数
    TreeNode root = new TreeNode(rootVal);
    root.left  = build(pre, preStart + 1,            preStart + leftSize,
                       in,  inStart,                 rootInIndex - 1, inToIndex);
    root.right = build(pre, preStart + leftSize + 1, preEnd,
                       in,  rootInIndex + 1,         inEnd,           inToIndex);
    return root;
}

三参数（len）版与上一版一一对应，k 即 rootInIndex：

private TreeNode dfs(int i, int j, int n) {
    if (n <= 0) return null;
    int v = pre[i];
    int k = inToIndex.get(v);
    TreeNode l = dfs(i + 1,         j,     k - j);            // leftSize
    TreeNode r = dfs(i + 1 + k - j, k + 1, n - 1 - (k - j));  // rightSize
    return new TreeNode(v, l, r);
}

两条不变量（写对就必然满足）：

preEnd - preStart == inEnd - inStart        两个窗口长度恒等
leftSize + 1 + rightSize == inEnd - inStart + 1

为什么 preorder 侧必须借 inorder 的数：仅凭 preStart/preEnd 无法确定切分点——preorder = [2,3] 既可能是「2 有左孩子 3」也可能是「2 有右孩子 3」，两种情况前序完全相同（in 分别为 [3,2] 和 [2,3]）。切分点信息只存在于中序。

易错点

  • pix（根在中序的下标）不能直接当前序的右边界。inorder 侧的区间可以直接用 pix 切（[inL, pix-1] / [pix+1, inR]），但 preorder 侧必须先换算成「左子树节点数」leftLen = pix - inL：左块 [preL+1, preL+leftLen]、右块 [preL+leftLen+1, preR]。写成 [preL+1, pix] / [pix+1, preR] 只在根节点那一层（preL == inL）碰巧正确，深层会重复包含根节点导致无限递归 / StackOverflow
  • 测试用例必须包含 preL != inL 的树：pre=[1,2,3], in=[2,3,1] 就能立刻暴露上述 bug；只有满二叉树、单链等对称用例会误判为「全过」
  • 用 Map<值, 中序下标> 预处理，把每层「找根位置」从 O(n) 降到 O(1)，总复杂度 O(n)；不预处理则最坏 O(n²)
  • 左子树前序终点写成 preL + leftSize + 1（多 1）也能 AC，实测 20000 次随机用例 0 失败、LeetCode 203/203。原因是：多出的那个位置在窗口末尾，而递归永远从 pre[preL]（头部）读根，读不到它；且每个调用消耗的位置数 1+leftSize+rightSize 恰好等于 inorder 窗口长度，所以 preL 走不到虚位。但这条正确性依赖 inL > inR 守卫——若只保留 preL > preR，实测立刻 ArrayIndexOutOfBoundsException。习惯上写 preL + leftSize，两个窗口长度自洽，单判 preL > preR 即可

  • 自查式：任何时候都应满足 preR - preL == inR - inL（两窗口长度相等）。左右子调用写完后代入验算，不等就说明边界写错

  • 前序中左子树范围的边界计算：preL + 1（左子树前序起点）到 preL + leftSize（左子树前序终点），preL + leftSize + 1（右子树前序起点）。多一个少一个都错

  • 中序的边界用 inL 和 inIdx，不要引入 inR，因为可以从 leftSize 反推
  • 没有重复值这个条件很重要——有重复值时无法确定根在中序中的位置，需要其他约束

面试追问

  • 为什么前序 + 中序能唯一确定一棵二叉树？ 前序提供根，中序提供左右划分——两序列各自贡献一部分信息。如果只给前序 + 后序，当树不是满二叉树时，结果不唯一
  • 不用 HashMap 的优化思路？ 每次在中序中线性查找根，最坏 O(n²)，但可以先答"Hash 优化到 O(n)"再简述"如果面试官说不准用额外空间，可以用双指针推进中序"

关联题