前序 + 中序重建二叉树：谁先被访问，左右各多少
前序只能告诉你「访问的顺序」，中序才能告诉你「根把左右分成了几块」。leftSize 是两份记录之间的桥。
递归处理中序区间 [L, R]：前序 preorder[preIndex] 是当前子树的根；在 inorder 中找到它的下标 mid，则左子树有 leftSize = mid − L 个节点。preIndex 消费根后按「左、右」顺序递归，L > R 时返回 nil。用哈希表把 mid 查询压到 O(1)。时间 O(n)，空间 O(n)。
给定一棵二叉树的前序遍历与中序遍历，重建这棵树，返回根节点。
前序「根、左、右」：第一个元素是根，但它完全无法告诉你左右子树各有多少个节点。
中序「左、根、右」：根的位置把整段数组切开——左边全是左子树，右边全是右子树。
这篇文章从「只有前序一份记录会怎样」开始，让你亲眼看到歧义，再让中序出手补上缺失的信息，最后把「取根、划界、递左、递右」落成一段递归代码。
两份记录，各自缺什么
输入是两段数组：preorder 是前序遍历（先访问根，再左子树，再右子树），inorder 是中序遍历（先左子树，再根，再右子树）。题目保证每个节点的值互不相同。
以示例为例：preorder = [3, 9, 20, 15, 7]，inorder = [9, 3, 15, 20, 7]。重建出来的树根是 3，它的左孩子是 9，右孩子是 20，而 20 的左孩子是 15、右孩子是 7。
先想清楚一个关键事实：中序的第一个元素不一定是最左叶子。inorder = [9, 3, 15, 20, 7] 的第一个元素是 9，但它不是整棵树的根——因为中序从最左的节点开始，而最左的节点恰恰可能是某个左子树的叶子。
这正是这道题的入口：两份记录各掌握一半信息，谁都不能单独复原整棵树。
只有前序：同一串数字，两种形状
先做个思想实验：给一份 preorder = [3, 9]，能确定这棵树长什么样吗？
「根 3，然后是 9」——9 可以是 3 的左孩子，也可以是 3 的右孩子。两种形状的前序遍历都是 [3, 9]，因为前序对「空子树」不做任何记录：空左子树不会留下占位符。
所以前序给出的信息是「谁先被访问」，而不是「节点挂在哪个方向」。方向信息一旦缺失，树就无法唯一确定。
关键缺口前序定顺序，不定方向。想要恢复方向，必须引入第二份能表达「左有多少、右有多少」的记录。
中序出手：根把区间切成两块
中序是「左、根、右」。一旦我知道了根是谁，就能在中序里找到它的位置 mid——mid 左边是左子树的所有节点，mid 右边是右子树的所有节点。
以整棵树为例：根是 3，inorder 里 3 的下标是 1，所以左子树只有 1 个节点（9），右子树有 3 个节点（15、20、7）。
但这里有个不对称：中序给出的是「左右各有几个」，前序给出的是「根后面紧跟着谁」。怎么把中序的计数带回前序？答案是 leftSize = mid − L：左子树有 leftSize 个节点，那么 preorder 里根后面的 leftSize 个元素就属于左子树，再往后全是右子树。
leftSize 是一座桥：它把中序的「分界」翻译成前序的「长度」。有了它，两份记录就能对齐，递归有了立足点。
leftSize中序算出「左边有几个」，前序据此知道「根后面几个元素归左」。一份信息补另一份的盲区。
递归施工单：dfs(L, R) 交付一棵子树
把上面的步骤打包成一个函数 dfs(L, R)，它的承诺是：给定中序区间 [L, R]，返回这棵子树完整的根节点。
施工步骤只有四步：消费 preorder[preIndex] 作为根；在 inorder 里查 mid；递归 dfs(L, mid−1) 建左子树并接到根左边；递归 dfs(mid+1, R) 建右子树并接到根右边。
边界条件 L > R：区间为空，说明这里没有节点，返回 nil。这是递归的出口——没有它，施工单会无限下发。
为什么「先左后右」的顺序如此重要？因为前序是「根、完整左子树、完整右子树」。必须先让 preIndex 消费完整个左子树的节点，它才会恰好停在右子树的根上。顺序错了，分界就全乱了。
调用顺序前序先列完整左子树，所以必须递左再递右；LC106 用后序时正好相反，要先递右。
为什么这样一定正确
归纳证明的关键是「不变式」：每次进入 dfs(L, R) 时，preIndex 恰好指向这棵子树在 preorder 中的根。基础情况：第一次调用，preIndex = 0，指向整棵树的根，成立。
递推：假设 dfs(L, mid−1) 前 preIndex 指向左子树根。左子树有 leftSize 个节点，消费完它们之后，preIndex 前进 leftSize 步，恰好指向右子树根——因为 preorder 的顺序就是「根、完整左子树、完整右子树」。
而 leftSize = mid − L 由中序唯一确定，与 preorder 无关，因此这个对齐永不漂移。每次递归要么区间缩小，要么触底 L > R 返回 nil，必然终止。
哈希表把「查 mid」从 O(n) 降到 O(1)：每个节点只进栈一次、出栈一次，整体 O(n)。
易错点与变式
最常见的错误是让 preIndex 在「找到 mid 之后」才递增，导致下一次调用消费错误的位置。正确的顺序是：先读根，立刻 preIndex++，再递归左右。
第二个坑是递归右子树前忘记先递左：一旦先递右，preIndex 会跳过整个左子树，分界立刻错位。
LC106 是这道题的镜像：后序是「左、右、根」，根在最后，所以必须从数组尾部开始消费，并且先递右再递左。
如果题目要求判空，别忘了入口处理：preorder 为空直接返回 nil；也可以让 dfs 处理 L > R 时返回 nil，由主函数统一收口。
面试表达先讲清「前序定顺序、中序定分界、leftSize 是桥」，再写代码，面试官会立刻知道你不是背模板。
Go：preIndex + indexMap
func buildTree(preorder, inorder []int) *TreeNode {pos := make(map[int]int, len(inorder))for i, v := range inorder { pos[v] = i }preIndex := 0var build func(int, int) *TreeNodebuild = func(L, R int) *TreeNode {if L > R { return nil }rootVal := preorder[preIndex]preIndex++root := &TreeNode{Val: rootVal}mid := pos[rootVal]root.Left = build(L, mid-1)root.Right = build(mid+1, R)return root}return build(0, len(inorder)-1)}
1值 → 中序下标表：mid 查询 O(1)。
2preIndex 是全局唯一的「前序消费指针」。
3区间为空：没有节点，返回 nil，递归出口。
4前序当前元素就是本子树根，先读后自增。
5中序定位根的位置，左右区间随之确定。
6先建左：让 preIndex 消费完左子树所有节点。
7再建右：此时 preIndex 恰好停在右子树根。
总结
前序定根、中序划界、leftSize 架桥；先左后右、空区间返回 nil。
- 前序只给访问顺序，不给左右边界——它单独存在必有歧义。
- 中序用根的位置切开区间，leftSize = mid − L 把计数带回前序。
- 先递左再递右，让 preIndex 顺序消费；L > R 是递归出口。
- LC106 用后序时反转：从尾消费、先右后左。