层序遍历（Level Order Traversal）
定义
层序遍历是二叉树按层级从上到下、每层从左到右遍历的方式。它是广度优先搜索（BFS）在二叉树上的应用。
void levelTraverse(TreeNode root) {
if (root == null) return;
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
int sz = q.size();
for (int i = 0; i < sz; i++) {
TreeNode cur = q.poll();
// 处理当前节点
System.out.println(cur.val);
if (cur.left != null) q.offer(cur.left);
if (cur.right != null) q.offer(cur.right);
}
}
}
核心特点
- 使用队列实现：先进先出（FIFO）保证按层级顺序访问
- BFS 算法的基础：扩展后可以处理图的最短路径问题
- 可以递归实现：通过传递层级参数或维护层级节点列表
递归实现（类似 BFS 思路）
// 方法一：传递深度参数
List<List<Integer>> res = new ArrayList<>();
void traverse(TreeNode root, int depth) {
if (root == null) return;
if (res.size() <= depth) {
res.add(new LinkedList<>());
}
res.get(depth).add(root.val);
traverse(root.left, depth + 1);
traverse(root.right, depth + 1);
}
// 调用：traverse(root, 0);
// 方法二：按层传递节点列表
void traverse(List<TreeNode> curLevelNodes) {
if (curLevelNodes.isEmpty()) return;
List<Integer> nodeValues = new LinkedList<>();
List<TreeNode> nextLevelNodes = new LinkedList<>();
for (TreeNode node : curLevelNodes) {
nodeValues.add(node.val);
if (node.left != null) nextLevelNodes.add(node.left);
if (node.right != null) nextLevelNodes.add(node.right);
}
res.add(nodeValues);
traverse(nextLevelNodes);
}
// 调用：traverse(Arrays.asList(root));
与 BFS 的关系
层序遍历是 BFS 算法在二叉树上的直接应用。BFS 算法框架正是从层序遍历代码扩展而来。
| 对比项 | 层序遍历 | BFS 算法 |
|---|---|---|
| 数据结构 | 队列 | 队列 |
| 应用场景 | 二叉树 | 图（无权图最短路径） |
| visited 数组 | 不需要（树无环） | 需要（图可能有环） |
| 核心思想 | 一层层扩散 | 一层层扩散 |
| 步数记录 | 可选 | 通常需要（最短路径） |
从层序遍历到 BFS 框架的演进：
// 二叉树层序遍历
void levelTraverse(TreeNode root) {
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
int sz = q.size();
for (int i = 0; i < sz; i++) {
TreeNode cur = q.poll();
// 处理 cur
if (cur.left != null) q.offer(cur.left);
if (cur.right != null) q.offer(cur.right);
}
}
}
// BFS 算法框架（扩展版）
int bfs(int start, int target) {
boolean[] visited = new boolean[graph.size()];
Queue<Integer> q = new LinkedList<>();
q.offer(start);
visited[start] = true;
int step = 0;
while (!q.isEmpty()) {
int sz = q.size();
for (int i = 0; i < sz; i++) {
int cur = q.poll();
if (cur == target) return step;
for (int to : neighborsOf(cur)) {
if (!visited[to]) {
q.offer(to);
visited[to] = true;
}
}
}
step++;
}
return -1;
}
关键区别：BFS 添加了 visited 数组防止成环，并增加了步数记录用于最短路径。
参见：BFS框架（BFS 框架完整讲解）