二叉树遍历学习手册
📖 目录
- 1. 适用场景
- 2. 核心原理
- 2.1 一句话口诀
- 2.2 代码位置决定遍历顺序
- 2.3 三种遍历对比表
- 3. 具体做法
- 3.1 递归模板（DFS）
- 3.2 迭代模板（栈模拟）
- 4. 实战案例：判断两棵树是否相同
- 4.1 问题描述
- 4.2 错误示范 & 为什么它能跑对
- 4.3 标准解法
- 5. 安全锁清单
- 5.1 null 到了边界，为什么还要往下走？
- 5.2 Python 的 and 短路会跳过另一半对比吗？
- 5.3 递归写法有哪些常见坑？
- 6. 进阶方向
1. 适用场景
二叉树遍历是几乎所有树相关问题的基础操作。你在以下场景中一定需要掌握遍历顺序：
| 场景 | 推荐遍历 | 原因 |
|---|---|---|
| 二叉搜索树（BST）升序输出 | 中序 | 中序遍历 BST = 有序序列 |
| 序列化 / 反序列化树 | 前序 | 根在前，方便重建树结构 |
| 计算树的高度 / 后序清理 | 后序 | 先处理子树，再处理根 |
| 层序打印 / 最短路径 | 层序（BFS） | 按层遍历，非本文范围 |
| 判断两棵树是否相同 | 前序同步对比 | 根→左→右同步推进 |
什么时候不用操心顺序？ 如果问题只关心"遍历所有节点"，不关心处理顺序（如累加所有节点值），前/中/后序都可以。
2. 核心原理
2.1 一句话口诀
前序（Pre-order）： 根 左 右 —— 根最先打印，进门先拜祖宗
中序（In-order）： 左 根 右 —— 根在中间打印，左子树干完再打印自己
后序（Post-order）： 左 右 根 —— 根最后打印，儿孙都处理完了再处理自己
假设永远 先左后右，只需要盯住 根节点（Root）何时被访问。
2.2 代码位置决定遍历顺序
在同一个递归函数里，print 写在三个不同位置，就产生三种顺序：
def dfs(node):
if node is None:
return
# 【位置 1】print 写在这里 → 前序（根左右）
print(node.val)
dfs(node.left)
# 【位置 2】print 写在这里 → 中序（左根右）
print(node.val)
dfs(node.right)
# 【位置 3】print 写在这里 → 后序（左右根）
print(node.val)
在一棵只有 3 个节点的树上（根 A，左 B，右 C），三种遍历结果：
前序：A B C
中序：B A C
后序：B C A
扩展到多节点树，同样的规律递归地应用到每个子树：
A
/ \
B C
/ \ / \
D E F G
前序：A B D E C F G
中序：D B E A F C G
后序：D E B F G C A
2.3 三种遍历对比表
| 遍历方式 | 口诀 | 根的位置 | 典型应用 | 一句话记忆法 |
|---|---|---|---|---|
| 前序 Pre-order | 根左右 | 最先 | 序列化、复制树 | 先处理自己，再处理孩子 |
| 中序 In-order | 左根右 | 中间 | BST 升序遍历 | 左子树搞定再打印自己 |
| 后序 Post-order | 左右根 | 最后 | 删除树、后序依赖计算 | 孩子都处理完再处理自己 |
3. 具体做法
3.1 递归模板（DFS）
三种遍历在递归中的区别仅仅是 print 的位置不同，框架完全一致：
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def traverse(root: TreeNode) -> List[int]:
"""前/中/后序模板：移动 print 位置即可切换"""
result = []
def dfs(node):
if node is None:
return
# 【前序】result.append(node.val)
dfs(node.left)
# 【中序】result.append(node.val)
dfs(node.right)
# 【后序】result.append(node.val)
dfs(root)
return result
3.2 迭代模板（栈模拟）
递归的本质是系统栈，手动用栈模拟就是迭代遍历。
前序（最直观）
根先入栈，每次弹出处理，然后先右后左入栈（栈后进先出，要保证左先处理）：
def preorder(root: TreeNode) -> List[int]:
if not root:
return []
stack, result = [root], []
while stack:
node = stack.pop()
result.append(node.val)
if node.right: # 右先入栈，左后入栈
stack.append(node.right) # 这样左先出栈，满足「根左右」
if node.left:
stack.append(node.left)
return result
中序（最需要理解）
指针一路向左到底，回溯时打印，然后转向右子树：
def inorder(root: TreeNode) -> List[int]:
stack, result = [], []
curr = root
while curr or stack:
while curr: # 一路向左，压入所有左子节点
stack.append(curr)
curr = curr.left
curr = stack.pop() # 弹出最左节点
result.append(curr.val) # 打印（左→根）
curr = curr.right # 转向右子树
return result
后序（技巧：前序变体 + 反转）
前序是 根左右，改成 根右左，再反转结果就是 左右根：
def postorder(root: TreeNode) -> List[int]:
if not root:
return []
stack, result = [root], []
while stack:
node = stack.pop()
result.append(node.val) # 根先
if node.left: # 左后入栈（和「前序」入栈顺序相反）
stack.append(node.left) # 右先出栈 → 顺序为根右左
if node.right:
stack.append(node.right)
return result[::-1] # 反转 → 左右根
三种迭代对比
| 遍历 | 核心思路 | 关键词 |
|---|---|---|
| 前序 | 根入栈 → 弹出处理 → 右左入栈 | 根最先 |
| 中序 | 指针一路向左 → 回溯打印 → 转向右 | 左到底 |
| 后序 | 按根右左入栈，结果反转 | 前序变体 |
4. 实战案例：判断两棵树是否相同
4.1 问题描述
给定两棵二叉树的根节点 p 和 q，判断它们是否完全相同（结构相同 + 节点值相同）。
4.2 一种分步写法（便于理解递归传递过程）
先看一个写法，它把「空值判断」和「值判断」拆成了三个独立分支：
class Solution:
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
def dfs_compare(check_node, compare_node):
if check_node and compare_node:
if check_node.val != compare_node.val:
return False
elif (check_node and not compare_node) or (not check_node and compare_node):
return False
else:
return True
# 👇 两个节点都非空 且 值相等时，走到这里继续递归
return dfs_compare(check_node.left, compare_node.left) and \
dfs_compare(check_node.right, compare_node.right)
return dfs_compare(p, q)
这段代码是正确的。 四个分支各自的执行路径：
| 条件 | 结果 | 是否走到递归调用？ |
|---|---|---|
| 都非空，但值不等 | return False |
❌ 提前返回 |
| 都非空，且值相等 | 不进入任何分支的 return | ✅ 执行递归 |
| 一个空一个不空 | return False |
❌ 提前返回 |
| 两个都空 | return True |
❌ 提前返回 |
为什么需要第 33 行的递归调用？ 它承担了两个角色：
- 向下钻 — 当前节点相等，继续对比左右子树是否也相等
- 向上传 — 子树的比对结果（True 或 False）通过
return逐层传回最外层
没有这行的话，函数只能对比根节点，深层的不匹配传不回来。
用 p = [1,2,3,null,4,5,null] 和 q = [1,2,3,null,null,6,null] 跑一遍，看看递归是怎么传递结果的：
树 p 树 q
1 1
/ \ / \
2 3 2 3
\ / / /
4 5 null 6
递归执行过程（关键帧）：
第 1 层：p=1, q=1 值相等 → 走递归调用
└── dfs_compare(left) ← 先算 and 的左操作数
第 2 层：p=2, q=2 值相等 → 走递归调用
├── dfs_compare(左) ← 先算 and 的左操作数
│ 第 3 层：null, null → else: return True ✅
└── dfs_compare(右) ← 再算 and 的右操作数
第 3 层：p=4, q=null → elif: return False ⚡
第 2 层：return True and False → return False
第 1 层收到左边 False → Python 短路 and，跳过右边，直接 return False
判定为 false 的关键： p 的节点 2 有右孩子 4，但 q 的节点 2 没有右孩子（null）—— 结构不对称在第 3 层被揪出来，靠 return dfs_compare(...) 一路传回最外层。
4.3 标准解法
class Solution:
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
# 【情景1】两个都空 → 到底了，相同
if not p and not q:
return True
# 【情景2】其中一个空 / 值不等 → 不同
if not p or not q or p.val != q.val:
return False
# 【情景3】递归对比左右子树，必须都 True
return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
代码逻辑映射：
| 情景 | 条件 | 返回值 | 含义 |
|---|---|---|---|
| A | not p and not q |
True |
同时越过了叶子节点 |
| B | not p or not q |
False |
结构不对称 |
| C | p.val != q.val |
False |
值不同 |
| D | 以上都不满足 | 递归对比左右 | 继续下钻 |
这套写法的优势：
- 只有 3 个分支，没有多余代码
- 递归调用在 return 里直接返回，不会产生死代码
- and 短路恰好表达"左右子树必须都相同"
5. 安全锁清单
5.1 null 到了边界，为什么还要往下走？
初学者常有的困惑："null 不是到底了吗？为什么还会有 False 返回？"
关键理解：null 只代表"当前这一条路"走到头了，父节点还有另一条路要对比。
2 ← 父节点
/ \
null 4 ← 右孩子还没对比呢！
递归不是一条直线，而是一个分叉。一个分支到边界后，函数回溯到父节点，父节点会继续走另一个分支。
5.2 Python 的 and 短路会跳过另一半对比吗？
会，但这正是我们想要的。
return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
- 如果左子树已经返回
False（结构不同），右子树根本不会执行 - 这是性能优化，不是 bug——左子树不同，整棵树必然不同
5.3 递归写法有哪些常见坑？
| 坑 | 现象 | 正确做法 |
|---|---|---|
if not p and not q 之后忘了 return |
递归进入 null 节点的左右孩子 → AttributeError |
一定要在条件分支里 return |
not p or not q 写在 p.val 判断之前 |
空指针访问 → 崩溃 | 先判空，再取值 |
p.val != q.val 写成 p.val != q.val and ... 再加递归 |
逻辑混乱 | 值不等直接 return False |
在 if 分支外写递归 |
死代码，永远不会执行（如 4.2 的错误示范） | 递归直接写在 return 里 |
6. 进阶方向
本文范围之外的扩展内容：
| 方向 | 简介 | 难度 |
|---|---|---|
| 层序遍历 | BFS 队列实现，按层输出节点 | ⭐ |
| Morris 遍历 | O(1) 空间复杂度的遍历，利用线索二叉树 | ⭐⭐⭐ |
| N 叉树遍历 | 前/后序推广到多叉树 | ⭐ |
| 遍历 + 回溯 | 在遍历过程中记录路径（如路径总和问题） | ⭐⭐ |
| 多树遍历对比 | 同时遍历两棵树（如 Same Tree、Subtree） | ⭐⭐ |
一句话总结： 前中后序的区别 =
No comments yet. Be the first!