【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）的顺序：

1. 先访问的节点，它的子节点也要先被访问

2. 这正是队列的特性

3.2 算法原理

text

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

3.3 手动模拟

以树为例：

text

3 / \ 9 20 / \ 15 7

执行过程：

步骤	队列状态	取出节点	访问结果	加入子节点
初始	[3]	-	-	-
1	[3]→[]	3	3	加入9,20 → [9,20]
2	[9,20]→[20]	9	9	无子节点
3	[20]→[]	20	20	加入15,7 → [15,7]
4	[15,7]→[7]	15	15	无子节点
5	[7]→[]	7	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 个节点，全部在队列中

八、常见应用场景

1. 树的层次结构展示：打印树形结构

2. 求树的高度/深度：层序遍历的层数

3. 求每层的最大值/平均值：统计每层数据

4. 二叉树的序列化：将树转换为字符串存储

5. 找到某层的最左/最右节点

6. 之字形遍历（Zigzag）：层序遍历的变种

九、完整代码模板

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接口

实现类	是否实现Queue	是否推荐用于层序遍历	原因
ArrayList	❌	❌	编译错误，不能用
LinkedList	✅	✅ 最常用	完美支持FIFO操作
ArrayDeque	✅	✅ 也可以	性能稍好，但不能存null

操作	存储的内容	类型	目的
队列中	节点的引用	TreeNode	需要访问节点结构（left/right）
结果列表中	节点的值	Integer	只需要输出数值
node变量	节点的引用	TreeNode	临时处理节点，可以访问子节点

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; } }

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

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