【LeetCode刷题日记】二叉树层序遍历完全指南：从基础到LeetCode实战一篇搞定BFS模板，秒杀4道经典面试题

 🔥个人主页：北极的代码（欢迎来访） 🎬作者简介：java后端学习者 ❄️个人专栏：苍穹外卖日记，SSM框架深入，JavaWeb ✨命运的结局尽可永在，不屈的挑战却不可须臾或缺！

前言：

我们继续对二叉树的相关知识进行学习，今天我们主要深入了解一下二叉树的层序遍历，以及层序遍历的模板和相关的算法题，让我们一起看看吧。

摘要：

本文深入讲解了二叉树的层序遍历（BFS）算法。

主要内容包括：1）层序遍历的定义，即按树的层级从上到下、从左到右访问节点；

2）与先序、中序、后序遍历的区别；

3）使用队列实现的核心思想，包括算法步骤和手动模拟示例；

4）分层输出的实现方法和重要性；

5）边界情况的处理；

6）时间/空间复杂度分析；

7）常见应用场景如打印树形结构、求树高等；

8）提供了完整的Java代码模板，并解释了关键数据结构；

9）结合LeetCode题目（102、107、199、637）展示实际应用。

文章通过图解和代码示例，帮助读者全面理解层序遍历的实现原理和应用技巧。

一、什么是层序遍历

层序遍历（Level Order Traversal）又称广度优先遍历（BFS，Breadth-First Search），是一种按照树的层级顺序，从上到下、从左到右依次访问每个节点的遍历方式。

直观理解

想象一棵树，从树根开始，先访问第1层，然后第2层，然后第3层…每一层内部从左到右访问。

text

1 ← 第1层
/ \\
2 3 ← 第2层
/ \\ / \\
4 5 6 7 ← 第3层

层序遍历结果：1, 2, 3, 4, 5, 6, 7

二、与其他遍历方式的对比

核心区别：层序遍历不按根左右的关系，而是按层次组织。

三、核心思想

3.1 为什么需要队列

层序遍历的关键是先进先出（FIFO，First In First Out）的顺序：

3.2 算法原理

text

步骤1：将根节点放入队列
步骤2：当队列不为空时，重复：
– 取出队首节点，访问它
– 将该节点的左子节点加入队列
– 将该节点的右子节点加入队列

3.3 手动模拟

以树为例：

text

3
/ \\
9 20
/ \\
15 7

执行过程：

最终结果：3, 9, 20, 15, 7

四、为什么用队列

4.1 队列的特性

java

队列的特点：
┌─────────────────────────────────────┐
│队尾 ← [新元素] [新元素] [新元素] ← 队首 │
│ (后进) (先进) │
│ │
│ offer() → 从队尾添加 │
│ poll() → 从队首取出 │
└─────────────────────────────────────┘

4.2 为什么不能用栈

如果使用栈（后进先出），会变成深度优先：

text

栈模拟（错误）：
初始：[3]
取出3，加入9,20 → [20,9]（注意顺序）
取出20，加入15,7 → [15,7,9]
取出15 → [7,9]
取出7 → [9]
取出9

结果：3,20,15,7,9 ← 不是层序遍历！

4.3 队列保证正确性

队列确保：

• 第1层的节点一定在第2层节点之前被访问

• 同一层内，左边的节点一定在右边节点之前被访问

五、分层输出的重要性

5.1 基本层序遍历 vs 分层输出

java

// 简单版：只输出序列
输出：3 9 20 15 7

// 分层版：区分每一层
输出：[[3], [9,20], [15,7]]

5.2 如何实现分层

核心技巧：在处理每层之前，记录当前队列的大小

java

while (!queue.isEmpty()) {
int levelSize = queue.size(); // 关键：当前层的节点数量

for (int i = 0; i < levelSize; i++) {
// 只处理当前层的节点
// 新加入的子节点属于下一层，本轮循环不会处理
}
}

5.3 分层原理图解

text

初始队列：[3]
levelSize = 1 ← 第1层有1个节点

处理节点3，加入子节点9,20
队列变：[9,20]

━━━━━━━━━━━━━━━━━━━━━━

levelSize = 2 ← 第2层有2个节点

处理节点9（无子节点）
处理节点20，加入子节点15,7
队列变：[15,7]

━━━━━━━━━━━━━━━━━━━━━━

levelSize = 2 ← 第3层有2个节点

处理节点15（无子节点）
处理节点7（无子节点）
队列变：[]

六、边界情况处理

6.1 空树

java

if (root == null) {
return new ArrayList<>(); // 返回空列表
}

6.2 只有根节点

java

queue = [3]
levelSize = 1
处理3，无子节点
queue = []
循环结束
结果：[[3]]

6.3 不完全二叉树

text

1
/ \\
2 3
/ \\
4 5

层序遍历：[[1], [2,3], [4,5]] ← 没有节点的地方跳过

七、时间与空间复杂度

最坏空间情况：

text

1
/ \\
2 3
/ \\ / \\
4 5 6 7
…
最后一层有 n/2 个节点，全部在队列中

八、常见应用场景

九、完整代码模板

java

public List<List<Integer>> levelOrder(TreeNode root) {
// 1. 结果集
List<List<Integer>> result = new ArrayList<>();

// 2. 边界处理
if (root == null) return result;

// 3. 初始化队列
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);

// 4. 层序遍历
while (!queue.isEmpty()) {
// 4.1 记录当前层节点数
int levelSize = queue.size();

// 4.2 存储当前层的值
List<Integer> currentLevel = new ArrayList<>();

// 4.3 处理当前层的所有节点
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.poll();
currentLevel.add(node.val);

// 4.4 将子节点加入队列（下一层）
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}

// 4.5 将当前层加入结果
result.add(currentLevel);
}

return result;
}

补充：

关于这些代码的细节：

List<List<Integer>> 是 Java 中的嵌套集合，可以理解为"列表的列表"。

直观理解

java

List<List<Integer>> result = new ArrayList<>();

这就像是一个二维数组，但更灵活：

text

result = [
[3], // 第0行
[9, 20], // 第1行
[15, 7] // 第2行
]

java

List<List<Integer>>
└─ List<…> // 外层：是一个List
└─ List<Integer> // 内层：每个元素又是一个List<Integer>
└─ Integer // 最内层：存储整数

继承关系：

text

Iterable
└── Collection
├── List
│ └── ArrayList ← 属于List体系
└── Queue
└── LinkedList ← 属于Queue体系
└── ArrayDeque ← 属于Queue体系

• ArrayList 实现了 List 接口

• LinkedList 同时实现了 List 和 Queue 接口

• ArrayDeque 实现了 Queue 接口

LeetCode算法题：

102.二叉树的层序遍历

具体代码就是上面说的

107.二叉树的层序遍历Ⅱ

整体思路是一模一样的，仅仅是结果翻转了而已，Collections.reverse(result);

199二叉树的右视图

这个题目也是在层序遍历的基础上进行细节处的修改，我们在从右边看的时候，只能看到每层的最后一个，也就是添加每层最后一个节点的值，而不是把每层的值都添加，由此就能得到我们想要的结果了。

if (i == levelSize – 1) {
result.add(node.val);
}
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> result=new ArrayList<>();
if(root==null){
return result;
}
Queue<TreeNode> queue=new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
int size =queue.size();
for(int i=0;i<size;i++){
TreeNode node =queue.poll();
if(i==size-1){
result.add(node.val);
}
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
}
return result;
}
}

需要注意的是，我们这里的返回值，并不需要二维集合，而是一维列表，因为每一层都只能看到一个节点，也就是返回的结果中每一层都是一个值，直接添加到结果中，不用考虑是哪一层。

637.二叉树的层平均值

/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Double> averageOfLevels(TreeNode root) {
List<Double> reuslt=new ArrayList<>();
if (root==null){
return reuslt;
}
Queue<TreeNode> queue=new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
int size=queue.size();
long sum=0;
for(int i=0;i<size;i++){
TreeNode node= queue.poll();
sum+=node.val;
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}

}
double average=(double)sum/size;
reuslt.add(average);

}
return reuslt;

}
}

这题的思路也很简单，我们只需要计算每层的平均值，然后返回到结果集中即可。

结语：如果对你有帮助，请点赞，关注，收藏 ，你的支持就是我最大的鼓励。