二叉树遍历基础
一句话总结
二叉树只有 递归遍历 和 层序遍历 这两种，再无其他。递归遍历可以衍生出 DFS 算法，层序遍历可以衍生出 BFS 算法。
核心内容
一、递归遍历（DFS）
1.1 遍历框架
递归遍历的核心是以下框架，遍历顺序固定（先左后右）：
// 基本的二叉树节点
class TreeNode {
int val;
TreeNode left, right;
}
// 二叉树的递归遍历框架
void traverse(TreeNode root) {
if (root == null) {
return;
}
// 前序位置
traverse(root.left);
// 中序位置
traverse(root.right);
// 后序位置
}
关键理解：
traverse函数的遍历顺序：一直往左子节点走 → 遇到空指针 → 尝试往右 → 再往左 → 左右子树都完成 → 返回父节点- 遍历顺序（root 指针移动顺序）仅取决于左右子节点的递归调用顺序，与其他代码无关
- 修改调用顺序（先右后左）会产生不同的遍历顺序，但一般不这样做
1.2 前序/中序/后序的本质
重要结论：递归遍历节点的顺序是固定的，但在不同位置写代码，效果不同。
| 位置 | 执行时机 | 效果 |
|---|---|---|
| 前序位置 | 刚进入节点时执行（对子节点一无所知） | 前序遍历结果 = root 指针移动顺序 |
| 中序位置 | 左子树遍历完成后，右子树遍历前执行 | 中序遍历结果 ≠ root 指针移动顺序 |
| 后序位置 | 左右子树都遍历完成后，即将离开节点时执行 | 后序遍历结果 ≠ root 指针移动顺序 |
可视化理解：
- 前序遍历：节点变绿的顺序（刚进入时）
- 中序遍历：节点变蓝的顺序（左子树完成后）
- 后序遍历：节点变红的顺序（左右子树都完成后）
1.3 关键性质
- 二叉搜索树（BST）的中序遍历结果是有序的，这是 BST 的重要性质
- 相关 LeetCode 题目：
二、层序遍历（BFS）
层序遍历：一层一层地遍历二叉树，需要借助队列实现。
2.1 写法一：简单版
void levelOrderTraverse(TreeNode root) {
if (root == null) {
return;
}
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
TreeNode cur = q.poll();
// 访问 cur 节点
System.out.println(cur.val);
// 把 cur 的左右子节点加入队列
if (cur.left != null) {
q.offer(cur.left);
}
if (cur.right != null) {
q.offer(cur.right);
}
}
}
缺点：无法知道当前节点在第几层。
2.2 写法二：记录层数（最常用）
void levelOrderTraverse(TreeNode root) {
if (root == null) {
return;
}
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
// 记录当前遍历到的层数（根节点视为第 1 层）
int depth = 1;
while (!q.isEmpty()) {
int sz = q.size(); // 关键：必须在循环开始前保存队列长度
for (int i = 0; i < sz; i++) {
TreeNode cur = q.poll();
// 访问 cur 节点，同时知道它所在的层数
System.out.println("depth = " + depth + ", val = " + cur.val);
if (cur.left != null) {
q.offer(cur.left);
}
if (cur.right != null) {
q.offer(cur.right);
}
}
depth++;
}
}
关键技巧：
sz = q.size()必须在for循环前保存，因为在循环过程中队列长度会变化- 可以用
while (sz-- > 0)替代for循环 - 这是最常用的层序遍历写法，可以解决"二叉树最小深度"等问题
2.3 写法三：带状态版（最灵活）
适用场景：每条树枝的权重可以是任意值（不只是 1），需要记录每个节点的路径权重和。
class State {
TreeNode node;
int depth;
State(TreeNode node, int depth) {
this.node = node;
this.depth = depth;
}
}
void levelOrderTraverse(TreeNode root) {
if (root == null) {
return;
}
Queue<State> q = new LinkedList<>();
q.offer(new State(root, 1));
while (!q.isEmpty()) {
State cur = q.poll();
// 访问 cur 节点，同时知道它的路径权重和
System.out.println("depth = " + cur.depth + ", val = " + cur.node.val);
if (cur.node.left != null) {
q.offer(new State(cur.node.left, cur.depth + 1));
}
if (cur.node.right != null) {
q.offer(new State(cur.node.right, cur.depth + 1));
}
}
}
应用场景：
- 多叉树的层序遍历
- 图的 BFS 遍历
- Dijkstra 算法
- 边带有权重的场景
三、其他遍历？
核心结论：二叉树的遍历方式只有上面两种，其他写法都是表现形式上的差异：
| 表现形式 | 本质 |
|---|---|
| 用栈迭代遍历二叉树 | 本质是递归遍历，手动维护栈模拟递归调用 |
| 递归地一层层遍历 | 本质是层序遍历，把 for 循环用递归形式展现 |
与后续算法的关系
| 二叉树遍历 | 衍生算法 | 说明 |
|---|---|---|
| 递归遍历框架 | DFS 算法、回溯算法 | 前中后序位置的思想延伸到深度优先搜索 |
| 层序遍历框架 | BFS 算法 | 队列 + 层数记录延伸到广度优先搜索 |