从中序与后序遍历序列构造二叉树

怎样从“inorder=[9,3,15,20,7] postorder=[9,15,7,20,3] 构造树。”推导出 二叉树 · 中后建树，并证明每次状态变化都不会漏掉答案？

中心结论：postIdx 倒序消费根→右→左;inorder 切区间;先递归右再左。

根据一棵树的中序遍历与后序遍历构造二叉树。

注意: 你可以假设树中没有重复的元素。

在本站主例中，inorder=[9,3,15,20,7] postorder=[9,15,7,20,3] 构造树。

算法最终需要得到或观察：根 3,左 9,右 20,20 的左 15 右 7。

从每个节点重新遍历子树会重复计算；递归让每棵子树只计算一次并向父节点返回摘要。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“递归回执树”，明确答案需要观察什么。
2. 2状态只维护 postIdx 尾指针、inorder 区间、递归栈 build(left,right)。
3. 3转移每一步按照 postIdx 倒序消费根→右→左;inorder 切区间;先递归右再左。
4. 4收尾读取 根 3,左 9,右 20,20 的左 15 右 7。，并复核边界与复杂度。

先用一句话定义递归函数返回什么，父节点才能正确合并。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：postIdx 尾指针、inorder 区间、递归栈 build(left,right)。

给出 2 个数组，根据 inorder 和 postorder 数组构造一颗树。 利用递归思想，从 postorder 可以得到根节点，从 inorder 中得到左子树和右子树。只剩一个节点的时候即为根节点。不断的递归直到所有的树都生成完成。

postIdx 倒序消费根→右→左;inorder 切区间;先递归右再左。

执行过程中持续维护：postIdx 尾指针、inorder 区间、递归栈 build(left,right)。

正确性依赖以下不变量：后序倒序消费时下一个节点是右子树根,必须先 build 右。

面试时可以压缩为：indexMap+postIdx倒序,node.Right=build(mid+1,right)先于Left,时间O(n)空间O(n)。

落到当前题，执行机制可以压缩为：postIdx 倒序消费根→右→左;inorder 切区间;先递归右再左。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入inorder=[9,3,15,20,7] postorder=[9,15,7,20,3] 构造树。 因为：postIdx 倒序消费根→右→左;inorder 切区间;先递归右再左。
2. 2后序:左-右-根适合「先处理子问题」的场景。 因为：删除树、算高度常用后序。
3. 3左右已完成,输出 7根最后写入。 因为：子树信息已汇总到当前结点。
4. 4预测下一步先不要看下一帧——根据当前不变量,预测算法接下来会怎么动。 因为：主动预测会暴露你对不变量的真实理解,比被动看动画有效得多。
5. 5左右已完成,输出 20根最后写入。 因为：子树信息已汇总到当前结点。
6. 6左右已完成,输出 3根最后写入。 因为：子树信息已汇总到当前结点。
7. 7后序:左-右-根适合「先处理子问题」的场景。 因为：删除树、算高度常用后序。
8. 8收尾与复杂度根 3,左 9,右 20,20 的左 15 右 7。 因为：时间 O(n) · 空间 O(n)。postIdx 倒序消费根→右→左;inorder 切区间;先递归右再左。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

// TreeNode define
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

// 解法一, 直接传入需要的 slice 范围作为输入, 可以避免申请对应 inorder 索引的内存, 内存使用(leetcode test case) 4.7MB -> 4.3MB.
func buildTree(inorder []int, postorder []int) *TreeNode {
	postorderLen := len(postorder)
	if len(inorder) == 0 {
		return nil
	}
	root := &TreeNode{Val: postorder[postorderLen-1]}
	postorder = postorder[:postorderLen-1]
	for pos, node := range inorder {
		if node == root.Val {
			root.Left = buildTree(inorder[:pos], postorder[:len(inorder[:pos])])
			root.Right = buildTree(inorder[pos+1:], postorder[len(inorder[:pos]):])
		}
	}
	return root
}

// 解法二
func buildTree1(inorder []int, postorder []int) *TreeNode {
	inPos := make(map[int]int)
	for i := 0; i < len(inorder); i++ {
		inPos[inorder[i]] = i
	}
	return buildInPos2TreeDFS(postorder, 0, len(postorder)-1, 0, inPos)
}

func buildInPos2TreeDFS(post []int, postStart int, postEnd int, inStart int, inPos map[int]int) *TreeNode {
	if postStart > postEnd {
		return nil
	}
	root := &TreeNode{Val: post[postEnd]}
	rootIdx := inPos[post[postEnd]]
	leftLen := rootIdx - inStart
	root.Left = buildInPos2TreeDFS(post, postStart, postStart+leftLen-1, inStart, inPos)
	root.Right = buildInPos2TreeDFS(post, postStart+leftLen, postEnd-1, rootIdx+1, inPos)
	return root
}

func main() {
    // 1. 主例
    //    输入：mode="postorder", values=[3,9,20,15,7]
    //    期望：根 3,左 9,右 20,20 的左 15 右 7。
    //
    // 2. 失败 / 未命中
    //    检查：勿照搬 LC105 先左后右;indexMap O(n) 空间不能写 O(1)。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC105 前中；LC889 前后
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意inorder=[9,3,15,20,7] postorder=[9,15,7,20,3] 构造树。
2. 2重复从每个节点重新遍历子树会重复计算；递归让每棵子树只计算一次并向父节点返回摘要。
3. 3优化postIdx 倒序消费根→右→左;inorder 切区间;先递归右再左。
4. 4证明后序倒序消费时下一个节点是右子树根,必须先 build 右。
5. 5复杂度时间 O(n)，空间 O(n)