LC94 · 中序遍历 · 工程执行实验室
左墙下潜法
中序遍历的本质是：每个节点都要等左子树处理完，才轮到自己。用 cur、stack、ans 三件套把访问时机讲清楚，而不是只背「左-根-右」。
输出：[1, 2, 3, 4, 5, 6]
核心 · 左墙下潜法
中序遍历的本质是：每个节点都要等左子树处理完，才轮到自己。
- · 一个节点不是看到就输出。
- · 必须先完成它的左子树。
- · 左子树完成后，才访问当前节点。
- · 当前节点访问后，才进入右子树。
迭代三件套
cur 是当前工作指针；stack 保存「左子树还没处理完」的节点；ans 是已输出序列。 内层循环一路向左压栈，外层弹栈访问后 cur 转向右子树。
递归其实也有栈，只是系统帮你藏起来了
- 1.递归代码里的 dfs(root.left) 会暂停当前函数，暂停状态保存在调用栈里。
- 2.等左子树返回后，才执行 ans.append(root.val)，再进入右子树。
- 3.迭代版只是把系统隐藏的调用栈，改成了我们自己维护的 stack。
1/13 · 题目区
关键步：
Step 0题目区
题目：中序遍历示例树，输出 [1,2,3,4,5,6]
给定二叉树：根 4，左子树 2-1-3，右子树 6-5。中序遍历不是背「左-根-右」口诀，而是弄清每个节点何时才能被访问。
为什么
访问时机比顺序口诀更重要：左子树未完成时，根节点不能输出。
状态表 · cur / stack / ans
| cur | stack（栈顶在右） | ans | 动作 | 原因 |
|---|---|---|---|---|
| cur = 4（节点 4） | [] | [] | 读题 | 目标序列 [1,2,3,4,5,6] |
cur 高亮·已访问·等待（描边）
Go · 递归版（直觉入口）
1func inorderTraversal(root *TreeNode) []int {2 ans := []int{}34 var dfs func(*TreeNode)5 dfs = func(node *TreeNode) {6 if node == nil {7 return8 }910 dfs(node.Left)11 ans = append(ans, node.Val)12 dfs(node.Right)13 }1415 dfs(root)16 return ans17}
展开迭代版（面试重点）
func inorderTraversal(root *TreeNode) []int {
ans := []int{}
stack := []*TreeNode{}
cur := root
for cur != nil || len(stack) > 0 {
for cur != nil {
stack = append(stack, cur)
cur = cur.Left
}
cur = stack[len(stack)-1]
stack = stack[:len(stack)-1]
ans = append(ans, cur.Val)
cur = cur.Right
}
return ans
}复杂度
- 时间
- O(n)
- 空间
- O(h)
每个节点最多入栈一次、出栈一次、访问一次，总共 O(n)。
h 为树高；最坏退化链表时 O(n)。递归版用系统调用栈，迭代版用显式 stack。
Morris 遍历可以做到额外空间 O(1)，但本页主线不讲 Morris。
面试回答
中序遍历的顺序是左子树、根节点、右子树。递归写法最直观：先 dfs(left)，再访问当前节点，再 dfs(right)。迭代写法用显式栈模拟递归调用栈：先一路向左，把经过的节点压栈；当左边走到底后，弹出栈顶访问；然后转向它的右子树。每个节点最多入栈出栈一次，所以时间 O(n)，栈空间 O(h)，最坏 O(n)。
常见误区
误区 1：看到节点就输出
中序不是「路过就打印」。必须先完成左子树，才轮到自己。
误区 2：弹栈后忘记 cur = cur.Right
访问当前节点后，下一步必须进入右子树，否则右子树会被漏掉。
误区 3：以为中序遍历一定有序
只有二叉搜索树 BST 的中序遍历才天然递增；普通二叉树只是按左-根-右顺序输出。
误区 4：空间复杂度写成 O(1)
递归/显式栈版本是 O(h)，最坏退化链表时 O(n)，不是 O(1)。