二叉树的中序遍历

怎样从“示例树根 4，左 2-1-3，右 6-5；中序输出 [1,2,3,4,5,6]。”推导出 二叉树 · 中序，并证明每次状态变化都不会漏掉答案？

中心结论：左墙下潜法：左子树处理完才访问根；迭代用显式栈模拟调用栈。

示例树根 4，左 2-1-3，右 6-5；中序输出 [1,2,3,4,5,6]。

在本站主例中，示例树根 4，左 2-1-3，右 6-5；中序输出 [1,2,3,4,5,6]。

算法最终需要得到或观察：中序序列 [1,2,3,4,5,6]。

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

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

1. 1建模把输入翻译成“递归回执树”，明确答案需要观察什么。
2. 2状态只维护 cur、显式 stack、ans 输出数组。
3. 3转移每一步按照 左墙下潜法：左子树处理完才访问根；迭代用显式栈模拟调用栈。
4. 4收尾读取 中序序列 [1,2,3,4,5,6]。，并复核边界与复杂度。

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

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：cur、显式 stack、ans 输出数组。

递归的实现方法，见代码。

左墙下潜法：左子树处理完才访问根；迭代用显式栈模拟调用栈。

执行过程中持续维护：cur、显式 stack、ans 输出数组。

正确性依赖以下不变量：每个节点都要等左子树处理完，才轮到自己。

面试时可以压缩为：中序遍历的顺序是左子树、根节点、右子树。递归写法最直观：先 dfs(left)，再访问当前节点，再 dfs(right)。迭代写法用显式栈模拟递归调用栈：先一路向左，把经过的节点压栈；当左边走到底后，弹出栈顶访问；然后转向它的右子树。每个节点最多入栈出栈一次，所以时间 O(n)，栈空间 O(h)，最坏 O(n)。

落到当前题，执行机制可以压缩为：左墙下潜法：左子树处理完才访问根；迭代用显式栈模拟调用栈。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入示例树根 4，左 2-1-3，右 6-5；中序输出 [1,2,3,4,5,6]。 因为：左墙下潜法：左子树处理完才访问根；迭代用显式栈模拟调用栈。
2. 2沿左子树压栈,cur=0左边界全部入栈。 因为：最后处理的才是最左结点。
3. 3沿左子树压栈,cur=3左边界全部入栈。 因为：最后处理的才是最左结点。
4. 4弹出并访问 2访问结点,转向右子树。 因为：左子树已全部处理完。
5. 5弹出并访问 3访问结点,转向右子树。 因为：左子树已全部处理完。
6. 6沿左子树压栈,cur=2左边界全部入栈。 因为：最后处理的才是最左结点。
7. 7弹出并访问 6访问结点,转向右子树。 因为：左子树已全部处理完。
8. 8收尾与复杂度中序序列 [1,2,3,4,5,6]。 因为：时间 O(n) · 空间 O(h)。左墙下潜法：左子树处理完才访问根；迭代用显式栈模拟调用栈。

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

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

func inorderTraversal(root *TreeNode) []int {
	var result []int
	inorder(root, &result)
	return result
}

func inorder(root *TreeNode, output *[]int) {
	if root != nil {
		inorder(root.Left, output)
		*output = append(*output, root.Val)
		inorder(root.Right, output)
	}
}

func main() {
    // 1. 主例
    //    输入：mode="inorder", values=[4,2,6,1,3,5]
    //    期望：中序序列 [1,2,3,4,5,6]。
    //
    // 2. 失败 / 未命中
    //    检查：看到节点就输出；弹栈后忘记 cur=Right；误以为中序一定有序；空间写成 O(1)。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC144 前序；LC145 后序
}

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

1. 1题意示例树根 4，左 2-1-3，右 6-5；中序输出 [1,2,3,4,5,6]。
2. 2重复从每个节点重新遍历子树会重复计算；递归让每棵子树只计算一次并向父节点返回摘要。
3. 3优化左墙下潜法：左子树处理完才访问根；迭代用显式栈模拟调用栈。
4. 4证明每个节点都要等左子树处理完，才轮到自己。
5. 5复杂度时间 O(n)，空间 O(h)