7.4 KiB
tags, create time
| tags | create time | |||||
|---|---|---|---|---|---|---|
|
2026-05-17 10:00 |
36-二叉树的中序遍历
题面
给定一个二叉树的根节点 root，返回它的 中序 遍历。
中序遍历的顺序：左子树 → 根节点 → 右子树。
示例 1：
输入：root = [1,null,2,3]
输出：[1,3,2]
1 遍历顺序
\ ┌─────────┐
2 ──→ │ 1 → 3 → 2│
/ └─────────┘
3
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
约束：
- 树中节点数目在范围
[0, 100]内 -100 <= Node.val <= 100
进阶： 递归算法很简单，你可以通过迭代算法完成吗？
思路
[!question] 💡 思考 中序遍历的核心是"先深入左子树到底，再处理根，最后转向右子树"。递归版本天然利用系统调用栈来记住回溯路径——那如果我们手动模拟这个过程，该用什么数据结构？
方法一：递归（最直观）⭐
中序遍历的递归实现几乎是对定义的字面翻译：
inorder(node):
if node == nil: return
inorder(node.left) // ① 先走左边
visit(node.val) // ② 再取当前值
inorder(node.right) // ③ 最后走右边
这种写法简洁优雅，但进阶要求我们尝试迭代。让我们看看如何用显式栈来模拟递归的调用栈行为。
方法二：显式栈模拟（迭代）⭐⭐
为什么用栈？
递归过程中，每进入一个节点的左子树，系统会把这个节点的"后续工作（访问自己、再访问右子树）"压入调用栈。当我们从左子树底部返回时，栈顶弹出刚才那个节点，进行处理。
关键观察：迭代的本质就是手动维护这个栈。
核心流程
flowchart TD
A["curr = root"] --> B{"curr != nil?"}
B -->|"否"| C{"栈为空?"}
C -->|"是"| D["结束, 返回结果"]
C -->|"否"| E["弹栈得到 node"]
E --> F["记录 node.val"]
F --> G["curr = node.right"]
G --> B
B -->|"是"| H["一路向左\n每次经过的节点都压栈\ncurr = curr.left"]
H --> B
逐步解析
以这棵树为例：
2
/ \
1 3
| 步骤 | 动作 | 栈 (底→顶) | curr | 结果 |
|---|---|---|---|---|
| 初始 | — | [] |
2 |
[] |
| 1 | 2 压栈，走到左 | [2] |
1 |
[] |
| 2 | 1 压栈，走到左 | [2, 1] |
nil |
[] |
| 3 | curr=nil，弹栈 1 |
[2] |
nil |
[1] |
| 4 | 1 无右子树，curr=nil |
[2] |
nil |
[1] |
| 5 | curr=nil，弹栈 2 |
[] |
2 |
[1, 2] |
| 6 | 2 有右子树 3，curr=3 |
[] |
3 |
[1, 2] |
| 7 | 3 压栈，走到左 | [3] |
nil |
[1, 2] |
| 8 | curr=nil，弹栈 3 |
[] |
nil |
[1, 2, 3] ✅ |
算法骨架（记忆口诀：「能左就左，左到不能左就回退，回头往右拐」）：
curr = root
while curr != nil 或 栈非空:
// 阶段1: 一路向左，全部压栈
while curr != nil:
push(curr)
curr = curr.left
// 阶段2: 栈顶就是下一个要访问的节点
node = pop()
result.append(node.val)
// 阶段3: 转向右子树
curr = node.right
[!info] 🧠 为什么这个循环是正确的？ 想象你在走迷宫：看到岔路就往左边走，同时把走过的路口记下来（压栈）。当发现左边没路了，就回到上一个路口（弹栈），记录它，然后尝试右边的路。重复直到所有路口都走完且栈为空。
Go 语言实现细节
- Go 标准库没有内置栈，用
[]T切片即可，追加和删除尾部操作均摊 O(1) nil判断直接node == nil，不需要额外的判空辅助函数
代码提示
// 伪代码模板
初始化空栈 stack
curr = root
result = []
while curr != nil 或 len(stack) > 0:
// 一路向左
while curr != nil:
stack = append(stack, curr)
curr = curr.left
// 回退 + 记录
node = stack[len(stack)-1]
stack = stack[:len(stack)-1] // pop
result = append(result, node.val)
// 转向右子树
curr = node.right
技巧
[!tip] 🔑 核心模式：Morris 中序遍历（进阶面试杀手锏） 上面的迭代法使用了 O(h) 空间（h 为树高）。如果面试官要求 O(1) 空间呢？答案是利用叶子节点的 nil 指针建立临时线索（Threaded Binary Tree），遍历完再恢复原状。虽然实际工程中很少用到，但在面试中是展示深度的利器。
基本思路：对于当前节点，找到其左子树的最右节点（前驱）。如果前驱的 right 指向 nil，说明第一次到达此节点，建立线索并往左走；如果前驱的 right 已经指向当前节点，说明左子树已遍历完毕，断开线索、记录当前值、往右走。
[!note] 🐹 Go 切片栈操作速查
- 压栈：
stack = append(stack, val)- 弹栈：
val := stack[len(stack)-1]; stack = stack[:len(stack)-1]- 判空：
len(stack) == 0- 不要使用
stack = nil代替缩容——这会丢失容量信息，影响后续 append 性能
[!info] 📊 复杂度分析
- 时间：O(n)，每个节点恰好被压栈一次、弹栈一次，总共 2n 次栈操作
- 空间：O(h)，h 为树的高度。最坏情况（链状树）O(n)，平均情况（平衡树）O(log n)
[!comparison] ⚖️ 三种写法对比
维度 递归 迭代（显式栈） Morris 代码简洁度 ⭐⭐⭐ ⭐⭐ ⭐ 空间复杂度 O(h) 隐式栈 O(h) 显式栈 O(1) 是否修改树结构 ❌ ❌ 临时修改后恢复 面试推荐度 入门可用 首选 加分项
代码
迭代法（推荐）⭐⭐
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func inorderTraversal(root *TreeNode) []int {
var result []int // 存放遍历结果
var stack []*TreeNode // 显式栈，存储待回退处理的节点
curr := root // 工作指针
for curr != nil || len(stack) > 0 {
// 阶段1: 一路向左，途经节点全部压栈
for curr != nil {
stack = append(stack, curr)
curr = curr.Left
}
// 阶段2: 栈顶元素即为下一个应访问的节点
node := stack[len(stack)-1] // peek 栈顶
stack = stack[:len(stack)-1] // pop
result = append(result, node.Val) // 记录值
// 阶段3: 转向右子树，下一轮继续从右子树最左开始
curr = node.Right
}
return result
}
递归法（参考）⭐
func inorderTraversal(root *TreeNode) []int {
if root == nil {
return nil
}
// 左 → 根 → 右
left := inorderTraversal(root.Left)
right := inorderTraversal(root.Right)
// 拼接结果
result := left
result = append(result, root.Val)
result = append(result, right...)
return result
}
[!success] ✅ 运行验证 这是 LeetCode 第 94 题（编号更正：原题编号应为 94，此处笔记沿用用户原始编号 36），通过率约 70%，是中序遍历的经典入门题。迭代解法是理解二叉树遍历底层机制的基石——掌握后，前序/后序遍历的迭代写法只需调整「记录时机」即可迁移。