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

RuntimeScope/算法实验台/56 天打卡/141 题/LC106

题型地图 56天全屏 141题

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

← LC105 LC107 →

44 / 141回到 Day 24 卡片 141 题索引

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

倒序消费 + 区间切分

inorder 像地图：根左边是左子树区间，根右边是右子树区间。postorder 从尾部向前消费，顺序是根 → 右 → 左，所以必须先递归 root.Right，再递归 root.Left——与 LC105 先左后右相反。

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

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

核心机制 · postIdx 倒序 + 区间

· inorder 负责确定左右子树边界：根左边是左子树中序，根右边是右子树中序。
· postorder 的最后一个元素是当前子树的根节点。
· postorder 从后往前消费时，顺序是：根 → 右 → 左（与后序遍历相反）。
· 因此代码里必须先递归 root.Right = build(mid+1, right)，再递归 root.Left = build(left, mid-1)。

倒序消费+区间地图

postorder 从尾部向前，消费顺序根→右→左；inorder 用 mid 把当前区间切成左右两半，递归边界由 left/right 控制。

rootVal := postorder[postIdx--]
mid := indexMap[rootVal] // 切 inorder
build(mid+1, right) · build(left, mid-1) // 先右后左

递归栈：先压右子树 build，再压左子树

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

常见错误：先左后右（照搬 LC105）

root.Left = build(left, mid-1)

root.Right = build(mid+1, right)

postorder 倒序读取时，下一个节点是右子树根，不是左子树根。如果先构造左子树，会把右子树节点错误塞进左边。

1/12 · 读题 · 双序列

12 步分镜：

Step 1读题 · 双序列

读题：postorder 倒序消费，inorder 切区间

给定中序 inorder 与后序 postorder，重建二叉树。与 LC105 不同：后序的最后一个元素是当前子树根；postIdx 从尾部向前移动，消费顺序是根→右→左，所以必须先递归右子树。inorder 仍负责切分左右区间。

· inorder 负责确定左右子树边界：根左边是左子树中序，根右边是右子树中序。
· postorder 的最后一个元素是当前子树的根节点。
· postorder 从后往前消费时，顺序是：根 → 右 → 左（与后序遍历相反）。
· 因此代码里必须先递归 root.Right = build(mid+1, right)，再递归 root.Left = build(left, mid-1)。

为什么

postorder 从后往前消费时，顺序是：根 → 右 → 左（与后序遍历相反）。

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

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

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

动作

读题inorder + postorder 双序列

postorder · 倒序消费·inorder · 区间地图·树 · 逐步挂载

递归栈 · build(left, right)

（空栈）

Go · buildTree

1func buildTree(inorder []int, postorder []int) *TreeNode {
2    indexMap := make(map[int]int)
3    for i, v := range inorder {
4        indexMap[v] = i
5    }
6    postIdx := len(postorder) - 1
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 := postorder[postIdx]
13        postIdx--
14        mid := indexMap[rootVal]
15        node := &TreeNode{Val: rootVal}
16        node.Right = build(mid+1, right)
17        node.Left = build(left, mid-1)
18        return node
19    }
20    return build(0, len(inorder)-1)
21}

复杂度

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

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

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

面试回答

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

常见误区

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

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

误区 2：先递归左子树（与 LC105 混淆）

postorder 倒序读取时，下一个节点是右子树根，不是左子树根。如果先构造左子树，会把右子树节点错误塞进左边。

误区 3：用切片拷贝 postorder/inorder

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

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

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

对任意 build(left, right)：postorder[postIdx] 一定是该 inorder 区间 [left, right] 对应子树的根；mid 把区间切成左段 [left, mid-1] 与右段 [mid+1, right]。倒序消费时下一个节点必属右子树，故先 build 右再 build 左。