5.3 树的遍历：递归、栈与队列
前置：二叉树基础、栈与队列，约 35 分钟。本节把访问时机转换成前序、中序、后序，再比较递归调用栈、显式栈和层序队列保存的状态。
分叉以后，顺序要由你定义
数组给出下标顺序，链表给出下一节点。树在一个节点处可能同时留下两条未走的分支。遍历算法要回答两个问题：
- 左右子树按什么次序处理。
- 当前节点在什么时候加入结果。
本页统一使用下面的样例：
1
/ \
2 3
/ \ \
4 5 6深度优先的三种访问时机
递归函数进入一个节点后，会经历三个位置：
位置 A：处理左子树之前
位置 B：左子树完成、右子树开始之前
位置 C：左右子树都完成之后把“记录当前 key”放在 A、B、C，就得到前序、中序、后序。
| 遍历 | 顺序 | 样例结果 | 常见用途 |
|---|---|---|---|
| 前序 | 根、左、右 | [1, 2, 4, 5, 3, 6] | 父节点先于孩子；复制或带空标记序列化 |
| 中序 | 左、根、右 | [4, 2, 5, 1, 3, 6] | BST 的升序 key；普通二叉树不保证有序 |
| 后序 | 左、右、根 | [4, 5, 2, 6, 3, 1] | 子结果先于父节点；目录大小、表达式树求值 |
仅记录前序值还不足以还原树：[1, 2] 不能说明节点 2 是左孩子还是右孩子。序列化若要保留结构，还需可与普通值区分的空链接标记。
递归与迭代完整实现
所有函数都返回新列表，空树返回 []，输入必须无环且没有共享孩子。迭代后序用 (node, expanded) 指示再次弹出节点时该做什么：先安排孩子，再返回当前节点。这比在列表头部反复插入更容易控制成本。
from collections import deque
class TreeNode:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def build_sample_tree():
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.right = TreeNode(6)
return root
def preorder_recursive(root):
result = []
def visit(node):
if node is None:
return
result.append(node.value)
visit(node.left)
visit(node.right)
visit(root)
return result
def inorder_recursive(root):
result = []
def visit(node):
if node is None:
return
visit(node.left)
result.append(node.value)
visit(node.right)
visit(root)
return result
def postorder_recursive(root):
result = []
def visit(node):
if node is None:
return
visit(node.left)
visit(node.right)
result.append(node.value)
visit(root)
return result
def preorder_iterative(root):
if root is None:
return []
result = []
stack = [root]
while stack:
node = stack.pop()
result.append(node.value)
if node.right is not None:
stack.append(node.right)
if node.left is not None:
stack.append(node.left)
return result
def inorder_iterative(root):
result = []
stack = []
current = root
while current is not None or stack:
while current is not None:
stack.append(current)
current = current.left
current = stack.pop()
result.append(current.value)
current = current.right
return result
def postorder_iterative(root):
if root is None:
return []
result = []
stack = [(root, False)]
while stack:
node, expanded = stack.pop()
if expanded:
result.append(node.value)
continue
stack.append((node, True))
if node.right is not None:
stack.append((node.right, False))
if node.left is not None:
stack.append((node.left, False))
return result
def level_order(root):
if root is None:
return []
result = []
queue = deque([root])
while queue:
node = queue.popleft()
result.append(node.value)
if node.left is not None:
queue.append(node.left)
if node.right is not None:
queue.append(node.right)
return result
def level_order_by_level(root):
if root is None:
return []
levels = []
queue = deque([root])
while queue:
level = []
for _ in range(len(queue)):
node = queue.popleft()
level.append(node.value)
if node.left is not None:
queue.append(node.left)
if node.right is not None:
queue.append(node.right)
levels.append(level)
return levels
sample = build_sample_tree()
pre = [1, 2, 4, 5, 3, 6]
ino = [4, 2, 5, 1, 3, 6]
post = [4, 5, 2, 6, 3, 1]
assert preorder_recursive(sample) == pre
assert preorder_iterative(sample) == pre
assert inorder_recursive(sample) == ino
assert inorder_iterative(sample) == ino
assert postorder_recursive(sample) == post
assert postorder_iterative(sample) == post
assert level_order(sample) == [1, 2, 3, 4, 5, 6]
assert level_order_by_level(sample) == [[1], [2, 3], [4, 5, 6]]手动跟一次迭代中序
目标顺序是左、根、右。算法先把从根到最左节点的路径压栈：
| 动作 | current | 栈（底→顶） | 结果 |
|---|---|---|---|
| 初始 | 1 | [] | [] |
| 压入 1 | 2 | [1] | [] |
| 压入 2 | 4 | [1, 2] | [] |
| 压入 4 | None | [1, 2, 4] | [] |
| 弹出 4 | None | [1, 2] | [4] |
| 弹出 2 | 5 | [1] | [4, 2] |
| 压入 5 后弹出 | None | [1] | [4, 2, 5] |
栈里保存的是“自身还没输出，稍后还要回来”的节点；有的左子树仍在处理，有的刚刚处理完。弹出节点后转向它的右子树，循环就能复用同一套规则。
前序为何先压右孩子
栈后进先出。前序要求左孩子先访问，所以迭代代码先压右，再压左：
push(right)
push(left)
pop() 先得到 left入栈次序要服从出栈方向，才能得到要求的遍历顺序。
后序为何需要状态
第一次见到节点 1 时不能立即输出，因为 2 和 3 尚未处理。迭代代码把 (1, True) 放回栈，意思是“孩子处理完后再回来输出 1”。随后压入右、左孩子，使左子树先执行。
另一种常见写法会生成根、右、左，再整体反转。它也能得到后序：result.reverse() 原地反转列表只需常数辅助空间，而 result[::-1] 会额外复制一个 Θ(n) 大小的列表。对 Python 列表反复使用 insert(0, value) 是 O(n) 单次移动，可能把完整遍历拖成 O(n²)。
广度优先与分层边界
层序遍历使用队列。处理当前节点时，把孩子放到队尾；先入队的浅层节点先出队。
分组层序在每轮开始时记录 len(queue)。这个长度就是当前层尚未处理的节点数。循环恰好取出这些节点，新入队的孩子留给下一轮。
时间和辅助空间
设节点数为 n、按边计的树高为 h、最大层宽为 w。下表针对非空树；空树返回仍需常数时间和空间：
| 遍历 | 时间 | 峰值辅助空间 | 峰值由什么决定 |
|---|---|---|---|
| 递归 DFS | O(n) | O(h + 1) | 调用栈上的根到当前节点路径 |
| 迭代 DFS | O(n) | O(h + 1) | 显式栈中的待处理祖先/分支 |
| 层序 BFS | O(n) | O(w) | 队列中相邻层的节点 |
O(w) 的通用上界可以写成 O(n)，但 w 更能解释实际占用。链状树的 w = 1，BFS 队列很小；一棵底层很宽的树会同时保存大量节点。
这里的 O(h+1) 是通用上界，不是每棵树上的紧界。例如本页迭代前序遍历单链时，栈里始终最多一个节点；带返回标记的后序在同一条链上却会保留祖先状态。
结果列表本身需要 Θ(n) 空间。复杂度表的“辅助空间”通常不计调用者要求的输出；写分析时要说明是否包含结果。
递归深度不是一个跨语言常数
旧代码常写“树深约 1000 就会溢出”，这只接近某些 CPython 默认配置的现象，不是算法或 Java 的保证。
- Python 用
sys.getrecursionlimit()查询当前解释器限制。限制用于保护 C 栈，不表示任意深度都能安全调高。 - Java 递归深度受线程栈大小、帧大小、JVM 和平台影响，没有固定的 1000 层规则。
- C++ 标准也不规定可用递归深度。
可能接收恶意深树、链状树或未知规模输入时，使用显式栈更容易控制失败方式。平衡数据结构则从源头限制 h。
Java 容器对应
Java 新代码实现 DFS 栈时可用 Deque<TreeNode> stack = new ArrayDeque<>();，调用 push、pop 和 peek。Oracle 文档认为 ArrayDeque 作为栈时通常可能快于旧的 Stack，这不是对每种负载的性能保证。
BFS 也可使用 ArrayDeque<TreeNode>，调用 offer 与 poll。本章讨论的是公开接口和算法状态，不依赖 LinkedList 的节点布局。
常见错误
递归函数复用默认列表
def inorder(node, result=[]) 会让多次调用共享列表。每次公开调用应创建新结果。
前序压栈顺序反了
先压左再压右，会先弹出右孩子，结果变成根、右、左。
中序访问位置提前
一进节点就加入结果是前序。中序要在左子树完成后访问当前节点。
后序只保存节点，不保存阶段
这份写法必须记录返回阶段，第一次弹出时不能直接输出。其他实现可以用上次访问节点的引用、反转结果或第二个栈等方式安排后序，但都要说清保存了什么状态。
层序把下一层混进当前层
分组输出时应在本轮入队孩子之前保存当前队列长度，不要让循环边界随着入队增长。
把 BST 结论套到普通树
样例树的中序结果不是升序。只有满足 BST 全局不变量时，中序才按 key 排序。
调试顺序
- 先写空树与单节点断言。
- 为样例树手算四个期望列表。
- 逐个比较递归版与迭代版输出。
- 在日志中打印栈或队列内容，不要只看最终结果。
- 测试只有左链、只有右链和缺一侧孩子的树。
- 分析空间时分别记录
h、w与输出长度。
动手比较四种遍历
- 手算样例树的四种遍历，不运行代码。
- 给迭代中序补全从节点 1 到节点 6 的状态表。
- 实现锯齿层序：偶数层从左到右，奇数层从右到左。
- 用后序递归计算每个节点的子树大小。
- 构造同为 31 个节点的链状树和完美树，比较 DFS 栈与 BFS 队列峰值。
比较顺序与待处理状态
递归、显式栈和队列保存的都是“接下来还要处理什么”，区别在于访问顺序和状态放在哪里。DFS 的峰值辅助空间上界随树高 h 变化，BFS 随最大层宽 w 变化；结果列表本身另占 O(n)。只有满足 BST 全局不变量时，中序结果才会按 key 有序。
若输入顺序把搜索树压成长链，下一章的 AVL 与旋转会说明怎样限制树高。