个人主页北极的代码欢迎来访作者简介java后端学习者❄️个人专栏苍穹外卖日记SSM框架深入JavaWeb✨命运的结局尽可永在不屈的挑战却不可须臾或缺前言我们继续对二叉树的相关知识进行学习今天我们主要深入了解一下二叉树的层序遍历以及层序遍历的模板和相关的算法题让我们一起看看吧。摘要本文深入讲解了二叉树的层序遍历BFS算法。主要内容包括1层序遍历的定义即按树的层级从上到下、从左到右访问节点2与先序、中序、后序遍历的区别3使用队列实现的核心思想包括算法步骤和手动模拟示例4分层输出的实现方法和重要性5边界情况的处理6时间/空间复杂度分析7常见应用场景如打印树形结构、求树高等8提供了完整的Java代码模板并解释了关键数据结构9结合LeetCode题目102、107、199、637展示实际应用。文章通过图解和代码示例帮助读者全面理解层序遍历的实现原理和应用技巧。一、什么是层序遍历层序遍历Level Order Traversal又称广度优先遍历BFSBreadth-First Search是一种按照树的层级顺序从上到下、从左到右依次访问每个节点的遍历方式。直观理解想象一棵树从树根开始先访问第1层然后第2层然后第3层...每一层内部从左到右访问。text1 ← 第1层 / \ 2 3 ← 第2层 / \ / \ 4 5 6 7 ← 第3层 层序遍历结果1, 2, 3, 4, 5, 6, 7二、与其他遍历方式的对比遍历方式访问顺序结果示例同上树层序遍历按层从左到右1, 2, 3, 4, 5, 6, 7先序遍历根→左→右1, 2, 4, 5, 3, 6, 7中序遍历左→根→右4, 2, 5, 1, 6, 3, 7后序遍历左→右→根4, 5, 2, 6, 7, 3, 1核心区别层序遍历不按根左右的关系而是按层次组织。三、核心思想3.1 为什么需要队列层序遍历的关键是先进先出FIFOFirst In First Out的顺序先访问的节点它的子节点也要先被访问这正是队列的特性3.2 算法原理text步骤1将根节点放入队列 步骤2当队列不为空时重复 - 取出队首节点访问它 - 将该节点的左子节点加入队列 - 将该节点的右子节点加入队列3.3 手动模拟以树为例text3 / \ 9 20 / \ 15 7执行过程步骤队列状态取出节点访问结果加入子节点初始[3]---1[3]→[]33加入9,20 → [9,20]2[9,20]→[20]99无子节点3[20]→[]2020加入15,7 → [15,7]4[15,7]→[7]1515无子节点5[7]→[]77无子节点最终结果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 如何实现分层核心技巧在处理每层之前记录当前队列的大小javawhile (!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 空树javaif (root null) { return new ArrayList(); // 返回空列表 }6.2 只有根节点javaqueue [3] levelSize 1 处理3无子节点 queue [] 循环结束 结果[[3]]6.3 不完全二叉树text1 / \ 2 3 / \ 4 5 层序遍历[[1], [2,3], [4,5]] ← 没有节点的地方跳过七、时间与空间复杂度复杂度值说明时间复杂度O(n)每个节点恰好访问一次空间复杂度O(n)最坏情况满二叉树最后一层有 n/2 个节点最坏空间情况text1 / \ 2 3 / \ / \ 4 5 6 7 ... 最后一层有 n/2 个节点全部在队列中八、常见应用场景树的层次结构展示打印树形结构求树的高度/深度层序遍历的层数求每层的最大值/平均值统计每层数据二叉树的序列化将树转换为字符串存储找到某层的最左/最右节点之字形遍历Zigzag层序遍历的变种九、完整代码模板java public ListListInteger levelOrder(TreeNode root) { // 1. 结果集 ListListInteger result new ArrayList(); // 2. 边界处理 if (root null) return result; // 3. 初始化队列 QueueTreeNode queue new LinkedList(); queue.offer(root); // 4. 层序遍历 while (!queue.isEmpty()) { // 4.1 记录当前层节点数 int levelSize queue.size(); // 4.2 存储当前层的值 ListInteger 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; }补充关于这些代码的细节ListListInteger是 Java 中的嵌套集合可以理解为列表的列表。直观理解java ListListInteger result new ArrayList();这就像是一个二维数组但更灵活textresult [ [3], // 第0行 [9, 20], // 第1行 [15, 7] // 第2行 ]java ListListInteger └─ List... // 外层是一个List └─ ListInteger // 内层每个元素又是一个ListInteger └─ Integer // 最内层存储整数继承关系textIterable └── 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 ListInteger rightSideView(TreeNode root) { ListInteger resultnew ArrayList(); if(rootnull){ return result; } QueueTreeNode queuenew LinkedList(); queue.offer(root); while(!queue.isEmpty()){ int size queue.size(); for(int i0;isize;i){ TreeNode node queue.poll(); if(isize-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 ListDouble averageOfLevels(TreeNode root) { ListDouble reusltnew ArrayList(); if (rootnull){ return reuslt; } QueueTreeNode queuenew LinkedList(); queue.offer(root); while(!queue.isEmpty()){ int sizequeue.size(); long sum0; for(int i0;isize;i){ TreeNode node queue.poll(); sumnode.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; } }这题的思路也很简单我们只需要计算每层的平均值然后返回到结果集中即可。结语如果对你有帮助请点赞关注收藏 你的支持就是我最大的鼓励。