Part 2.5：二叉树遍历：理解树的四种核心视角

引言：如何“阅读”一棵树？

在上一篇文章中，我们了解了树的基本结构。现在，我们面临一个更实际的问题：如何访问树中的每一个节点？就像我们阅读一本书需要按一定顺序（从前到后）翻页一样，我们也需要一种系统性的方法来访问树中的所有节点，这个过程就叫做**树的遍历 (Tree Traversal)**。

与线性结构不同，树的非线性特性决定了其遍历方式不止一种。选择不同的遍历顺序，就像从不同的视角去观察和理解这棵树，会得到完全不同的节点序列。每种序列都有其独特的用途。

为什么树的遍历如此重要？

• 面试核心：树的遍历是算法面试中必考的知识点，没有之一。无论是直接让你实现四种遍历，还是在更复杂的题目中（如判断对称二叉树、求树的最大深度、序列化和反序列化二叉树），其核心都离不开遍历的思想。
• 算法基石：遍历是几乎所有树相关操作的基础。搜索、插入、删除、修改树节点，都首先需要通过遍历找到目标位置。
• 思维训练：学习树的遍历，特别是其递归和迭代（非递归）两种实现方式，是训练递归思维和栈/队列应用能力的绝佳途径。

本文将带你深入探索二叉树的四种核心遍历方法：前序、中序、后序（深度优先）和层序（广度优先），让你彻底掌握这门“读树”的艺术。

背景知识：两种遍历策略

树的遍历策略主要分为两大类：

1. **深度优先搜索 (Depth-First Search, DFS)**：尽可能深地探索树的分支。当一个节点的所有子树都被访问过之后，才回溯到其父节点。前序、中序、后序遍历都属于 DFS。
2. **广度优先搜索 (Breadth-First Search, BFS)**：从根节点开始，先访问完同一层的所有节点，再进入下一层。层序遍历属于 BFS。

Part A：深度优先搜索 (DFS) 的三种视角

对于二叉树的 DFS 遍历，其核心在于根节点 (Root) 的访问时机。我们以 R 代表访问根节点，L 代表遍历左子树，R 代表遍历右子树。

1. 前序遍历 (Pre-order): R -> L -> R

口诀：根、左、右。

直觉：像一个领导视察工作，先到办公室（根节点）报到，然后去左边的部门视察，最后去右边的部门视察。对于每个子部门，也遵循同样的视察流程。

动画式案例

遍历过程：

1. 访问根 F。
2. 遍历左子树（以 B 为根）：
   1. 访问 B。
   2. 遍历左子树（以 A 为根）：访问 A。
   3. 遍历右子树（以 D 为根）：访问 D，然后访问 C，再访问 E。
3. 遍历右子树（以 G 为根）：
   1. 访问 G。
   2. （无左子树）
   3. 遍历右子树（以 I 为根）：访问 I，然后访问 H。

最终序列：F, B, A, D, C, E, G, I, H

实现方式

递归实现 (Recursive)

def preorder_recursive(root):
    if not root:
        return
    print(root.value)      # 1. 访问根节点
    preorder_recursive(root.left)  # 2. 遍历左子树
    preorder_recursive(root.right) # 3. 遍历右子树

迭代实现 (Iterative) - 使用栈

思路：用一个栈来模拟递归的过程。

1. 将根节点入栈。
2. 当栈不为空时，弹出一个节点并访问它。
3. 先将右子节点入栈，再将左子节点入栈。（因为栈是 LIFO，后入的左子节点会先被访问）

def preorder_iterative(root):
    if not root:
        return
    stack = [root]
    while stack:
        node = stack.pop()
        print(node.value)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)

应用场景：常用于创建树的副本或序列化树，因为先访问根节点可以方便地确定结构。

2. 中序遍历 (In-order): L -> R -> R

口诀：左、根、右。

直觉：像一个中尉，总是先让左边的士兵报数，然后自己报数，最后让右边的士兵报数。

动画式案例

使用与前序遍历相同的树。

遍历过程：

1. 一直向左，直到最左边的叶子节点 A。访问 A。
2. 回溯到 B，访问 B。
3. 进入 B 的右子树（以 D 为根）。先访问其最左边的 C，然后是 D，最后是 E。
4. 左子树遍历完毕，回溯到根 F，访问 F。
5. 进入右子树（以 G 为根）。它没有左子树，所以直接访问 G。
6. 进入 G 的右子树（以 I 为根）。先访问其左子 H，然后是 I。

最终序列：A, B, C, D, E, F, G, H, I

实现方式

递归实现

def inorder_recursive(root):
    if not root:
        return
    inorder_recursive(root.left)   # 1. 遍历左子树
    print(root.value)       # 2. 访问根节点
    inorder_recursive(root.right)  # 3. 遍历右子树

迭代实现 - 使用栈

思路：

1. 循环将当前节点及其所有左子节点入栈。
2. 当无法再往左时，弹出一个节点并访问它。
3. 将当前节点转向其右子节点，重复步骤 1。

def inorder_iterative(root):
    stack = []
    current = root
    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        print(current.value)
        current = current.right

应用场景：在二叉搜索树 (BST) 中，中序遍历可以得到一个有序的节点序列。这是它最重要的特性。

3. 后序遍历 (Post-order): L -> R -> R

口诀：左、右、根。

直觉：像一个下级向上级汇报工作。必须先听完左边下属的汇报，再听完右边下属的汇报，最后自己总结，向自己的上级汇报。

动画式案例

使用与前序遍历相同的树。

遍历过程：

1. 深入到最左边的子树，直到叶子节点 A。访问 A。
2. 回溯到 B，进入其右子树（以 D 为根）。
3. 在 D 的子树中，先访问左子 C，再访问右子 E，最后访问 D。
4. B 的左右子树都已访问，现在访问 B。
5. 回溯到根 F，进入其右子树（以 G 为根）。
6. 在 G 的子树中，先访问其右子树（以 I 为根）。在 I 的子树中，先访问左子 H，然后访问 I。
7. G 的右子树已访问，现在访问 G。
8. 根 F 的左右子树都已访问，最后访问 F。

最终序列：A, C, E, D, B, H, I, G, F

实现方式

递归实现

def postorder_recursive(root):
    if not root:
        return
    postorder_recursive(root.left)  # 1. 遍历左子树
    postorder_recursive(root.right) # 2. 遍历右子树
    print(root.value)       # 3. 访问根节点

迭代实现 - 使用栈

后序的迭代实现最复杂。一个巧妙的方法是改造前序遍历。
前序是“根-左-右”，我们可以实现一个“根-右-左”的遍历，然后将结果反转，就得到了“左-右-根”的后序遍历。

def postorder_iterative(root):
    if not root:
        return
    stack = [root]
    result = []
    while stack:
        node = stack.pop()
        result.append(node.value)
        # 与前序相反，先压入左子节点
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    # 反转结果
    print(result[::-1])

应用场景：常用于计算或销毁。例如，计算一个目录的总大小（必须先计算完所有子目录的大小），或者释放一棵树的内存（必须先释放子节点才能释放父节点）。

Part B：广度优先搜索 (BFS) 的唯一视角

4. 层序遍历 (Level-order)

口诀：从上到下，从左到右。

直觉：像水波纹一样，从中心（根节点）开始，一圈一圈地向外扩散。

动画式案例

使用与前序遍历相同的树。

遍历过程：

1. 第 1 层: 访问 F。
2. 第 2 层: 访问 B, G。
3. 第 3 层: 访问 A, D, I。
4. 第 4 层: 访问 C, E, H。

最终序列：F, B, G, A, D, I, C, E, H

实现方式 - 使用队列

思路：用一个队列来存储待访问的节点。

1. 将根节点入队。
2. 当队列不为空时，出队一个节点并访问它。
3. 将其所有子节点（先左后右）依次入队。

from collections import deque

def levelorder(root):
    if not root:
        return
    queue = deque([root])
    while queue:
        node = queue.popleft() # 从队列头部取出
        print(node.value)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

应用场景：非常适合解决最短路径问题（在无权图中），或者需要按层级处理的问题（如找到树的最小深度）。

Part C：从遍历到解题

掌握了遍历，我们就可以解决很多问题。例如，一个经典的面试题：

“已知一棵二叉树的前序遍历和中序遍历，重建这棵二叉树。”

解题思路：

1. 前序遍历的第一个元素永远是根节点。
2. 在中序遍历中找到这个根节点，其左边的所有元素都属于左子树，右边的所有元素都属于右子树。
3. 这样我们就把问题分解成了构建左子树和右子树两个子问题，可以递归解决。

复杂度分析总结

对于一棵有 n 个节点的二叉树：

遍历方式	时间复杂度	空间复杂度 (递归)	空间复杂度 (迭代)
前序遍历	O(n)	O(h)	O(h)
中序遍历	O(n)	O(h)	O(h)
后序遍历	O(n)	O(h)	O(h)
层序遍历	O(n)	-	O(w)

• h 是树的高度。最好情况 h=log n，最坏情况 h=n。
• w 是树的最大宽度。最坏情况 w 可能接近 n。

总结

树的遍历是理解和操作树结构的核心与前提。今天我们学习了四种遍历方式，它们从不同的视角“解读”了树的结构。

• **深度优先 (DFS)**：
  • **前序 (根-左-右)**：适合复制和序列化。
  • **中序 (左-根-右)**：在 BST 中可得有序序列。
  • **后序 (左-右-根)**：适合计算和销毁。
• **广度优先 (BFS)**：
  • **层序 (按层)**：适合找最短路径和按层级处理。

熟练掌握这四种遍历的递归和迭代实现，是每一个合格程序员的必备技能。在下一篇文章中，我们将学习一种特殊的完全二叉树——堆，以及它的重要应用——优先队列。