二叉树的遍历是指按照某种特定的顺序访问树中的每一个节点，且每个节点只被访问一次。常见的遍历方法主要分为两大类：深度优先搜索（DFS）和广度优先搜索（BFS）。

  • 深度优先搜索 (DFS)：尽可能深地搜索树的分支。根据根节点被访问的顺序，又分为前序遍历、中序遍历和后序遍历。
  • 广度优先搜索 (BFS)：又称为层序遍历，从根节点开始，逐层地访问节点。

1. 前序遍历 (Pre-order Traversal)

访问顺序：根 (Root) -> 左 (Left) -> 右 (Right)

核心思想：首先访问根节点，然后递归地前序遍历左子树，最后递归地前序遍历右子树。

递归实现思路：

1
2
3
4
5
6
7
8
9
10
11
12
13

function preorder(node):

if node is null:

return

visit(node) // 访问根节点

preorder(node.left) // 遍历左子树

preorder(node.right) // 遍历右子树

迭代实现思路（使用栈）：

  1. 将根节点入栈。
  2. 循环直到栈为空：
    a. 弹出栈顶节点 node 并访问它。
    b. 先将 node 的右子节点（如果存在）入栈。
    c. 再将 node 的左子节点（如果存在）入栈。（注意：先入右再入左，保证出栈时先左后右）

适用情况与题型

  1. 树的复制/序列化：

    • 分析：前序遍历的顺序（根-左-右）非常适合构建树。在序列化时，可以方便地标记空节点（例如用 # 表示）。反序列化时，第一个值就是根，然后递归地构建左子树和右子树。
    • 题型举例：LeetCode 297. 二叉树的序列化与反序列化
    • 示例：树 [1, 2, 3, null, null, 4] 序列化为 "1,2,#,#,3,4,#,#,"。

  2. 确定树的结构（例如前缀表达式）：

    • 分析：表达式树的前序遍历结果即为前缀表达式（波兰表达式）。
    • 题型举例：构建表达式树或根据树生成前缀表达式。

  3. 文件系统遍历：

    • 分析：类似于操作系统的目录遍历，先访问当前目录（根），然后依次进入子目录（左、右...）。

2. 中序遍历 (In-order Traversal)

访问顺序：左 (Left) -> 根 (Root) -> 右 (Right)

核心思想：首先递归地中序遍历左子树，然后访问根节点，最后递归地中序遍历右子树。

递归实现思路：

1
2
3
4
5
6
7
8
9
10
11
12
13

function inorder(node):

if node is null:

return

inorder(node.left) // 遍历左子树

visit(node) // 访问根节点

inorder(node.right) // 遍历右子树

迭代实现思路（使用栈）：

  1. 初始化一个栈 stack 和一个指针 curr 指向根节点。
  2. 循环条件：curr 不为空或 stack 不为空。
  3. 内部循环（向左走到底）：当 curr 不为空时，将 curr 入栈，并令 curr = curr.left。
  4. （curr 为空，说明左子树到底了）从 stack 弹出一个节点 node，访问 node。
  5. 令 curr = node.right（转向右子树）。

适用情况与题型

  1. 二叉搜索树 (BST) 的排序输出：

  2. 获取有序数据：

    • 分析：当需要将树中的元素按某种“中间”逻辑（通常是大小）排序时，中序遍历是首选。

3. 后序遍历 (Post-order Traversal)

访问顺序：左 (Left) -> 右 (Right) -> 根 (Root)

核心思想：首先递归地后序遍历左子树，然后递归地后序遍历右子树，最后访问根节点。

递归实现思路：

1
2
3
4
5
6
7
8
9
10
11
12
13

function postorder(node):

if node is null:

return

postorder(node.left) // 遍历左子树

postorder(node.right) // 遍历右子树

visit(node) // 访问根节点

迭代实现思路（使用两个栈或一个栈 + 标记）：
一个较巧妙的方法是利用前序遍历（根-左-右）的变种（根-右-左），然后将结果反转，即得到（左-右-根）。

  1. 修改迭代前序遍历：入栈顺序改为先左后右。
  2. 访问顺序变为：根 -> 右 -> 左。
  3. 将访问结果存储起来，最后反转该结果。

适用情况与题型

  1. 树的销毁（释放内存）：

    • 分析：必须先处理（销毁）完左右子节点后，才能销毁根节点，否则会丢失对子节点的引用。后序遍历的顺序（左-右-根）完美符合这个要求。
    • 题型举例：涉及释放树节点内存的系统编程。

  2. 依赖子树结果的计算（树型 DP）：

  3. 计算后缀表达式（逆波兰表达式）：

    • 分析：表达式树的后序遍历结果即为后缀表达式。

4. 层序遍历 (Level-order Traversal / BFS)

访问顺序：按层（从上到下）遍历，每层从左到右访问。

核心思想：使用队列（Queue）来实现广度优先搜索 (BFS)。

迭代实现思路（使用队列）：

  1. 初始化一个队列 queue，将根节点入队。
  2. 循环直到队列为空：
    a. 获取当前队列的大小 levelSize（即当前层的节点数）。
    b. 循环 levelSize 次：
    i.   将队首节点 `node` 出队并访问它。
ii.  将 `node` 的左子节点（如果存在）入队。
iii. 将 `node` 的右子节点（如果存在）入队。
    c. （levelSize 次循环结束，表示当前层已访问完毕）

适用情况与题型

  1. 按层打印树：

  2. 寻找最短路径（在树中）：

    • 分析：BFS 的特性是能找到从起点到终点的最短路径（在图中）。在树中，它常用于查找最小深度。
    • 题型举例：LeetCode 111. 二叉树的最小深度（注意：最小深度是从根到叶子节点的最短路径）。

  3. 获取特定层的信息：

总结

遍历方法 访问顺序 核心应用场景 典型题型
前序遍历 根 -> 左 -> 右 树的序列化、复制、构建 LeetCode 297 (序列化)
中序遍历 左 -> 根 -> 右 二叉搜索树 (BST) LeetCode 98 (验证BST), 230 (BST第K小)
后序遍历 左 -> 右 -> 根 依赖子树结果的计算 (树型DP)、释放内存 LeetCode 104 (最大深度), 110 (平衡二叉树), 124 (最大路径和)
层序遍历 (BFS) 按层（上->下, 左->右） 按层处理、最短路径（最小深度） LeetCode 102 (层序遍历), 199 (右视图), 111 (最小深度)

关键技巧：

  • 前序 + 中序 或 后序 + 中序 可以唯一确定一棵二叉树（前提是树中没有重复元素）。
  • 前序 + 后序 无法唯一确定一棵树。
  • 解决二叉树问题时，首先思考 “对于当前节点 node，我需要从它的左、右子树获取什么信息？”
    • 如果需要先处理子树才能得到当前节点的结果 -> 后序遍历（树型 DP）。
    • 如果处理顺序和子树无关，或者需要从上到下传递信息 -> 前序遍历。
    • 如果和 BST 的大小顺序相关 -> 中序遍历。
    • 如果和“层”、“深度”、“宽度”相关 -> 层序遍历 (BFS)。