如何从前序和中序遍历序列重建二叉树？

简化版

前序的第一个元素一定是根。拿这个根值去中序里定位，它把中序分成左半段（左子树）和右半段（右子树），两段长度就告诉你前序里哪些属于左、哪些属于右。然后对左右两部分递归重建。用哈希表存「中序值 → 下标」可快速定位，整体 O(n)。

详细版

两个关键性质：

前序（根左右）：第一个是根，紧接着是「左子树的前序」，再是「右子树的前序」。
中序（左根右）：根左边全是左子树、右边全是右子树。

重建步骤：

取前序第一个值 rootVal 作为根。
在中序里找到 rootVal 的位置 i，i 左边有 leftSize = i - inStart 个节点，是左子树。
前序里，根之后的 leftSize 个是左子树的前序，再往后是右子树的前序。
对左右两部分递归。

Map<Integer, Integer> idx = new HashMap<>();   // 中序值 → 下标，O(1) 定位根
public TreeNode buildTree(int[] preorder, int[] inorder) {
    for (int i = 0; i < inorder.length; i++) idx.put(inorder[i], i);
    return build(preorder, 0, preorder.length - 1, 0, inorder.length - 1);
}
TreeNode build(int[] pre, int preL, int preR, int inL, int inR) {
    if (preL > preR) return null;
    int rootVal = pre[preL];
    TreeNode root = new TreeNode(rootVal);
    int i = idx.get(rootVal);              // 根在中序中的位置
    int leftSize = i - inL;                // 左子树节点数
    root.left  = build(pre, preL + 1, preL + leftSize, inL, i - 1);
    root.right = build(pre, preL + leftSize + 1, preR, i + 1, inR);
    return root;
}

完整版教学

一、为什么前序 + 中序能唯一确定一棵树

前序告诉你「谁是根」（每个子树的第一个元素）。
中序告诉你「根的左边有哪些、右边有哪些」（划分左右子树）。

两者配合：前序定根、中序分左右，递归下去每一层都能确定根和左右子树的范围，于是整棵树被唯一还原。单独一个前序或中序做不到（无法划分左右），必须两者结合。

注意：前序 + 后序无法唯一确定一棵二叉树（缺少划分左右的信息，可能有歧义）；而前序+中序、后序+中序都可以。原因就是中序提供了「根两侧即左右子树」这个划分依据。

二、下标范围的推导（最容易错的地方）

设当前处理前序区间 [preL, preR]、中序区间 [inL, inR]：

根是 pre[preL]，在中序里位置为 i。
左子树节点数 leftSize = i - inL。
左子树：前序 [preL+1, preL+leftSize]，中序 [inL, i-1]。
右子树：前序 [preL+leftSize+1, preR]，中序 [i+1, inR]。

这几个边界靠 leftSize 串起来。写错一个 +1 或 -1 就会重建失败，建议在纸上用小例子（如前序 [3,9,20,15,7]、中序 [9,3,15,20,7]）验证一遍。

三、用哈希表加速定位根

朴素做法每次在中序里线性扫描找根，是 O(n)，总复杂度 O(n²)。用一个 HashMap 预存「中序值 → 下标」，定位根变成 O(1)，整体降到 O(n)。前提是节点值不重复（否则无法用值唯一定位，这也是这类题通常给的假设）。

四、走一遍小例子

前序: [3, 9, 20, 15, 7]
中序: [9, 3, 15, 20, 7]

根 = 3（前序首个），在中序中位置 i=1
  左子树: 中序[9] → 前序[9]         → 节点 9
  右子树: 中序[15,20,7] → 前序[20,15,7]
     根 = 20，中序中位置分出 左[15]、右[7]
结果:
        3
       / \
      9   20
         /  \
        15   7

五、同类变体

中序 + 后序重建：后序的最后一个是根，其余同理（后序是「左右根」）。
前序 + 后序重建：只能重建，但结果可能不唯一（无法区分某些左/右单子树的情况），题目通常会说明返回任意一个合法解。

六、常见误区与追问

组合	能否唯一重建	关键原因
前序 + 中序	能	前序给根，中序划分左右子树
后序 + 中序	能	后序给根，中序划分左右子树
前序 + 后序	通常不能	缺少单子树在左还是在右的信息

易错点：重建题真正考的是「区间切分」而不是建节点语法。leftSize 算错一位，后面的递归区间会全部错位。

误区：前序和后序也一定能唯一重建。 对于只有一个孩子的节点，前序和后序无法区分孩子在左边还是右边，所以一般不唯一。
误区：可以不建中序下标表，复杂度也还是 O(n)。 每次在线性扫描中序找根，递归层层扫描，最坏会到 O(n²)；哈希表把定位根降为 O(1)。
误区：有重复值也能直接按值建 HashMap。 重复值会导致一个值对应多个中序位置，题目通常默认节点值不重复；如果有重复值，需要额外唯一标识。
追问：为什么 leftSize = i - inL？ 因为中序区间 [inL, i-1] 全是左子树，元素个数正好是 i - inL。
追问：递归终止条件怎么写？ 当前前序区间为空即可返回 null，常见写法是 preL > preR，同时中序区间也会同步为空。
追问：空间复杂度是多少？ 哈希表 O(n)，递归栈 O(h)；总空间通常写 O(n)，因为哈希表占主导。

七、加强记忆

前序+中序重建：前序首元素是根，拿它在中序里定位，中序被分成左段（左子树）、右段（右子树），据两段长度把前序也切成左右两部分，递归重建。用哈希表存「中序值→下标」把定位降到 O(1)、整体 O(n)。核心边界靠 leftSize = 根在中序的位置 − inL。注意：前序+后序不能唯一确定树，前序/后序 + 中序才行。

简化版

详细版