LC105 从前序与中序遍历序列构造二叉树 · 逐题动画 · RuntimeScope

当前：LC105 · 从前序与中序遍历序列构造二叉树 · 首次出现于 Day 24 · 路径：顶栏「56天打卡」→ 点击 LC 题号 → 逐题动画

LC105 · 前序 + 中序构造二叉树 · 工程执行实验室

发号机 + 区间地图

preorder 像发号机：每次给出当前子树的根， preIndex 只向前走。inorder 像地图：根左边是左子树区间，根右边是右子树区间。 left/right 标记当前 inorder 边界，left > right 时返回 nil。

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

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

核心机制 · preIndex + 区间

· preorder 像发号机：每次给出当前子树的根，preIndex 只向前走、不回头。
· inorder 像地图：根左边是左子树区间，根右边是右子树区间。
· left > right 时当前子树为空，直接返回 nil。
· 为什么 preorder 的下一个数就是根？因为前序遍历总是「根 → 左 → 右」，进入任意子树时第一个数一定是该子树根。

发号机+区间地图

preorder 按「根→左→右」发号，preIndex 依次消费；inorder 用 mid 把当前区间切成左右两半，递归边界由 left/right 控制。

rootVal := preorder[preIndex++]
mid := indexMap[rootVal] // 切 inorder
build(left, mid-1) · build(mid+1, right)

递归栈：build(left, right) 压栈，子树完成弹栈

1.build(0,4) 取根 3 后，先压 build(0,0) 造左子树，再压 build(2,4) 造右子树。
2.build(2,4) 内部同样：build(2,2) 造 15，build(4,4) 造 7。
3.left > right 时不压栈，直接 return nil。

1/12 · 读题 · 双序列

12 步分镜：

Step 1读题 · 双序列

读题：preorder 发号，inorder 切区间

给定前序 preorder 与中序 inorder，重建二叉树。前序像发号机——按「根→左→右」顺序依次给出每棵子树的根；中序像地图——根左边是左子树、右边是右子树。preIndex 只向前走，left/right 标记当前正在构造的 inorder 区间。

· preorder 像发号机：每次给出当前子树的根，preIndex 只向前走、不回头。
· inorder 像地图：根左边是左子树区间，根右边是右子树区间。
· left > right 时当前子树为空，直接返回 nil。
· 为什么 preorder 的下一个数就是根？因为前序遍历总是「根 → 左 → 右」，进入任意子树时第一个数一定是该子树根。

为什么

preorder 像发号机：每次给出当前子树的根，preIndex 只向前走、不回头。

状态表 · preIndex / 区间 / 递归栈

preIndex	rootVal	[left, right]	mid	左区间	右区间	调用栈
0	—	[0, 4]	—	∅	∅	[]

当前 inorder 切片：[9, 3, 15, 20, 7]

动作

读题preorder + inorder 双序列

preorder · 发号机·inorder · 区间地图·树 · 逐步挂载

递归栈 · build(left, right)

（空栈）

Go · preIndex + indexMap

1func buildTree(preorder []int, inorder []int) *TreeNode {
2    indexMap := make(map[int]int)
3    for i, v := range inorder {
4        indexMap[v] = i
5    }
6    preIndex := 0
7    var build func(left, right int) *TreeNode
8    build = func(left, right int) *TreeNode {
9        if left > right {
10            return nil
11        }
12        rootVal := preorder[preIndex]
13        preIndex++
14        mid := indexMap[rootVal]
15        node := &TreeNode{Val: rootVal}
16        node.Left = build(left, mid-1)
17        node.Right = build(mid+1, right)
18        return node
19    }
20    return build(0, len(inorder)-1)
21}

复杂度

时间: O(n)
空间: O(n)

每个节点只处理一次：读 preorder[preIndex]、查 indexMap、递归左右各一次。

indexMap 占 O(n)；递归栈最坏退化链表 O(n)，平衡树约 O(log n)。不是 O(1)。

面试回答

预处理 inorder 值→下标 indexMap。preIndex 全局递增，build(left,right) 中 left>right 返回 nil；rootVal=preorder[preIndex++]，mid=indexMap[rootVal]；node.Left=build(left,mid-1)，node.Right=build(mid+1,right)。时间 O(n)，空间 O(n)（map + 栈）。

常见误区

误区 1：空间复杂度写成 O(1)

用了 indexMap O(n) 和递归栈 O(h)，总体 O(n)，不能写 O(1)。

误区 2：用切片拷贝 preorder/inorder

每次递归 pre[1:] 或 in[:mid] 会产生 O(n²) 拷贝。正确做法是用 preIndex + left/right 区间。

误区 3：忘记 left > right 的递归基

空子树对应 inorder 区间 left > right，必须 return nil，否则会死循环或建错节点。

误区 4：mid 切分搞反

左子树是 inorder[left..mid-1]，右子树是 inorder[mid+1..right]。mid 位置的值已经给了根，不能重复进左右。