当前位置：首页 > ds >正文

层序遍历（BFS）核心逻辑：从二叉树到复杂题型的一通百通

ds 2025/5/16 17:17:59

一、层序遍历的本质：用队列模拟层级扩散

层序遍历的核心是广度优先搜索（BFS），其本质是模拟“水波扩散”的过程：

队列作为“扩散容器”：每次处理一层节点（当前水波范围），将下一层节点（下一圈水波）暂存到队列中。
层级隔离：通过记录当前层的节点数（levelSize = queue.size()），确保每轮循环只处理同一层节点，避免不同层级节点混合。

核心代码框架（以二叉树为例）：

Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {int levelSize = queue.size(); // 当前层节点数for (int i = 0; i < levelSize; i++) {TreeNode node = queue.poll(); // 处理当前层节点// 子节点入队（下一层扩散）if (node.left != null) queue.offer(node.left);if (node.right != null) queue.offer(node.right);}// 处理完一层后，可收集当前层数据或进行其他操作
}

二、题型串联：从“数据收集”到“结构操作”的逻辑演变

所有基于层序遍历的题目，都是在上述框架基础上，对**“节点处理逻辑”和“结果收集方式”**进行定制。我们按题型分类解析：

第一类：层数据收集（输出层相关结果）

核心逻辑：在每层循环结束后，根据需求收集当前层的特定数据

1. 基础层序遍历（102题）

目标：收集每一层的所有节点值。

操作：在每层循环中，将节点值存入临时列表，循环结束后添加到结果列表。

List<Integer> currentLevel = new ArrayList<>();
for (...) { currentLevel.add(node.val); }
result.add(currentLevel);

2. 逆序层序遍历（107题）

目标：从下到上输出层数据。
关键修改：将当前层结果插入到结果列表的头部（或最后统一反转）。
```
result.add(0, currentLevel); // 每次插入头部，自然逆序
```

3. 层平均值/最大值（637题、515题）

目标：计算层统计值。
逻辑：
- 平均值：累加层内节点值，除以节点数。
- 最大值：遍历层内节点时更新最大值。
```
double sum = 0;
for (...) { sum += node.val; }
result.add(sum / levelSize); // 平均值
```

4. 二叉树右视图（199题）

目标：每层最右侧节点的值（最后一个出队的节点）。
逻辑：层内循环时，当处理到最后一个节点（i == levelSize - 1）时收集值。
```
if (i == levelSize - 1) result.add(node.val);
```

第二类：树结构操作（修改节点连接关系）

核心逻辑：利用层序遍历的顺序性，在层内或层间建立节点关联

1. 填充next指针（116题、117题）

目标：将同一层节点按从左到右顺序用next指针连接。
逻辑：
- 层内维护前一个节点引用（prev），每次处理节点时，将prev.next指向当前节点。
- 完美二叉树（116题）：可直接通过队列的下一个节点（queue.peek()）建立连接。
- 普通二叉树（117题）：需处理跨层空节点，仅在同层节点间连接。
```
Node prev = null;
for (...) {if (prev != null) prev.next = node;prev = node;
}
```

第三类：树深度计算（统计层级相关属性）

核心逻辑：利用层序遍历的“天然分层”特性，统计层数或最短/最长路径

1. 最大深度（104题）

目标：根节点到最远叶子节点的层数。
逻辑：每处理完一层，深度加1（初始深度为0，每层循环后深度+1）。
```
int depth = 0;
while (...) {// 处理一层节点depth++;
}
```

2. 最小深度（111题）

目标：根节点到最近叶子节点的层数。
关键优化：遇到叶子节点（left==null && right==null）时，直接返回当前深度，提前终止遍历。
```
for (...) {if (node是叶子节点) return depth;
}
```

第四类：数据结构扩展（从二叉树到N叉树）

核心逻辑：通用层序遍历框架，仅需调整子节点入队方式

N叉树层序遍历（429题）

差异：二叉树处理left/right，N叉树遍历所有子节点（children列表）。

代码调整：

for (Node child : node.children) {queue.offer(child); // 入队所有子节点
}

三、核心逻辑总结：万变不离其宗的“三层抽象”

抽象层	基础框架逻辑	题型定制点
队列初始化	根节点入队	无
层级循环	`while(队列非空)`	无
层内处理	`for(当前层节点数)`	节点值收集、指针连接、深度统计等
子节点入队	二叉树：`left/right`入队	N叉树：遍历所有子节点入队
结果处理	保存当前层数据	逆序、统计值、取特定位置值等

四、典型错误与避坑指南

1. 层节点数获取时机错误

错误：在子节点入队后获取queue.size()，导致levelSize包含下一层节点。
正确：在层循环开始前获取levelSize = queue.size()，确保仅统计当前层节点。

2. 混淆层序遍历与深度优先搜索（DFS）

层序遍历（BFS）：天然按层级顺序处理，适合需要“逐层”操作的场景（如统计层数据、建立层内连接）。
DFS：适合需要“深入路径”的场景（如路径总和问题）。
判断依据：题目中出现“层”“行”“同一层级”等关键词时，优先考虑层序遍历。

3. 忽略空树边界条件

处理：在代码入口处添加if (root == null) return xxx;，避免空指针异常。

五、从“会做一题”到“通解一类”的思维升级

剥离问题本质：所有层序遍历题目均可拆解为“遍历框架”+“业务逻辑”。
- 框架不变：队列入队/出队、层节点数控制。
- 业务逻辑可变：收集值、计算统计量、修改节点关系等。

抽象通用模板：

public void levelOrder(TreeNode root) {if (root == null) return;Queue<TreeNode> q = new LinkedList<>();q.offer(root);while (!q.isEmpty()) {int s = q.size();for (int i=0; i<s; i++) {TreeNode node = q.poll();// 定制化逻辑（核心变化点）process(node); // 子节点入队（可能变化，如N叉树）enqueueChildren(node); }// 层结果处理（可能变化，如逆序、统计）handleLevelResult(); }
}