LeetCode 102. 二叉树的层序遍历 | BFS 分层模板逐行拆解 + 易错点全复盘

前言二叉树的层序遍历是广度优先搜索BFS的入门经典题也是面试超高频考点。最开始接触层序遍历时我们通常先学会「出队→访问→孩子入队」的朴素一维流程而本题要求按层返回二维列表本质是在朴素 BFS 的基础上增加了「按层切块」的技巧核心的入队出队逻辑完全一致。本篇完整记录从朴素层序遍历到分层版本的思路演变逐行拆解定稿代码梳理所有新手高频踩坑点吃透这道 BFS 母题后续的锯齿形遍历、二叉树右视图、每层最大值等变体题都能快速推导。一、题目与考点拆解题目要求给你二叉树的根节点root返回其节点值的层序遍历。即逐层地从左到右访问所有节点每一层的节点值单独放在一个子列表中。输入二叉树根节点输出二维列表外层按层级排列内层为每一层从左到右的节点值核心考点这道题本质考察的是BFS 广度优先搜索的工程实现核心落点在三个能力队列「先进先出」特性的运用实现按层级顺序访问分层技巧通过提前记录每层节点数实现批量按层处理边界处理空树、叶子节点无孩子等场景的空指针防护最优解为队列迭代法时间复杂度 O (n)每个节点入队出队各一次空间复杂度 O (n)队列最多存储最底层的所有节点。二、思路演变从朴素遍历到分层遍历1. 朴素层序遍历一维结果这是最基础的 BFS 流程也是我们最初学习的版本根节点先入队循环中队首节点出队并访问有孩子则左右依次入队直到队列为空。// 朴素版输出一维列表不分层 public ListInteger simpleLevelOrder(TreeNode root) { ListInteger res new ArrayList(); if (root null) return res; QueueTreeNode queue new ArrayDeque(); queue.add(root); while (!queue.isEmpty()) { TreeNode node queue.poll(); res.add(node.val); // 左右孩子依次入队 if (node.left ! null) queue.add(node.left); if (node.right ! null) queue.add(node.right); } return res; }这个版本逻辑完全正确但只能输出所有节点的平铺列表无法区分节点属于哪一层。2. 分层遍历的核心技巧题目要求二维分层结果我们只需要在朴素流程上加一个关键设计每一轮 while 循环开始时队列里恰好装着「当前整层的全部节点」。 我们提前把当前层的节点数量固定下来用内层 for 循环只处理对应数量的节点就能严格做到「一次 while 循环处理一整层」。处理当前层节点的过程中下一层的子节点会陆续加入队列但因为循环次数已经提前锁定它们不会被本轮处理会留到下一轮 while 循环天然实现层级隔离。三、专属定稿 AC 代码import java.util.*; class Solution { public ListListInteger levelOrder(TreeNode root) { // 最终结果二维列表每层对应一个子列表 ListListInteger res new ArrayList(); // BFS核心工具队列ArrayDeque性能更优且不允许存null QueueTreeNode queue new ArrayDeque(); // 根节点非空才入队天然处理空树边界避免空指针 if (root ! null) { queue.add(root); } // 外层循环每一轮完整处理一层节点 while (!queue.isEmpty()) { // 【分层核心】提前锁定当前层节点总数禁止边循环边取size int levelSize queue.size(); // 临时列表收集当前层的所有节点值 ListInteger level new ArrayList(); // 内层循环只处理当前层固定循环levelSize次 for (int i 0; i levelSize; i) { // 队首节点出队 TreeNode node queue.poll(); // 访问当前节点存入当前层列表 level.add(node.val); // 左孩子非空则入队 if (node.left ! null) { queue.add(node.left); } // 右孩子非空则入队 if (node.right ! null) { queue.add(node.right); } } // 当前层全部处理完毕归档到结果集 res.add(level); } // 返回分层结果 return res; } }四、逐行深度拆解1. 结果集合初始化ListListInteger res new ArrayList();题目要求分层返回因此是二维列表结构外层列表的每个元素对应一整层的节点值子列表。使用ArrayList适配尾部追加的使用场景初始为空集合对应空树的默认结果。2. 队列初始化QueueTreeNode queue new ArrayDeque();层序遍历依赖队列「先进先出」的特性保证节点按入队顺序被访问也就是按层级、从左到右的顺序。 这里选用ArrayDeque作为实现类有两个优势底层是动态数组没有链表节点的额外对象开销入队出队性能优于LinkedList天然不允许存储 null 元素倒逼我们必须判空后再入队从源头规避空节点问题3. 根节点入队if (root ! null) { queue.add(root); }这一行同时解决两个问题空树边界处理root 为空时队列保持为空后续 while 循环不会执行直接返回空集合逻辑自洽无需额外写提前返回。适配 ArrayDeque 特性ArrayDeque不支持添加 null直接入队空根节点会触发空指针异常必须先判空。4. 外层 while 循环while (!queue.isEmpty()) {循环条件为队列非空。每进入一轮循环队列里恰好装着完整的一层节点一轮循环结束该层所有节点处理完毕下一层节点全部入队。队列为空时代表所有节点都已访问遍历结束。5. 提前记录当前层节点数分层核心int levelSize queue.size();这是整道题最核心、最容易写错的一行必须重点理解进入循环时队列里只有当前层的所有节点此时的queue.size()就是当前层的节点总数。为什么必须提前存成固定变量 处理节点的过程中下一层的子节点会不断加入队列queue.size()是动态变化的。如果把queue.size()直接写在 for 循环条件里循环次数会持续变大把下一层节点也提前处理彻底打乱层级。提前把数量锁死内层循环只跑固定次数就能严格保证「一次循环只处理一层」。6. 当前层临时列表ListInteger level new ArrayList();专门收集当前层的节点值每轮 while 循环新建一个处理完当前层后整体归档到结果集。7. 内层 for 循环for (int i 0; i levelSize; i) {循环次数严格等于当前层节点数只处理当前层的节点。它和朴素版的区别只是「把节点按层打包处理」核心的出队、入队逻辑完全没有变化。8. 节点出队与访问TreeNode node queue.poll(); level.add(node.val);poll()移除并返回队首元素对应「节点出队」操作将节点值加入当前层列表就是「访问节点」的操作业务场景中可替换为任意处理逻辑9. 左右孩子依次入队if (node.left ! null) { queue.add(node.left); } if (node.right ! null) { queue.add(node.right); }对应朴素版的核心逻辑有孩子就左右依次入队。两个关键细节先左后右队列先进先出左孩子先入队就会先被处理保证每一层从左到右的访问顺序写反则顺序错误。必须判空叶子节点无孩子空节点不能入队 —— 既会触发ArrayDeque的空指针异常后续出队取val也会报错。注意这里入队的是下一层节点会排在当前层剩余节点的后面不会影响本轮 for 循环的次数这就是分层的巧妙之处。10. 当前层归档res.add(level);内层循环结束当前层所有节点处理完毕将该层列表整体加入最终结果完成一层的遍历。11. 返回结果return res;所有层级处理完成返回分层的二维列表。五、新手必踩坑清单坑 1根节点不判空直接入队现象空树时触发空指针异常原因ArrayDeque不允许存 null直接add(root)会在 root 为空时报错坑 2for 循环条件直接写queue.size()现象分层失效所有节点挤在同一个子列表里原因处理过程中队列长度动态变化循环次数会把下一层节点也算进来坑 3子节点不判空就入队现象遇到叶子节点时空指针异常原因空节点进入队列出队取val时直接崩溃坑 4先右后左入队现象每层节点顺序颠倒变成从右到左原因队列先进先出先入队的节点会先被访问坑 5用 Stack 代替 Queue现象变成深度优先遍历顺序完全错误原因栈是后进先出和层序遍历的访问顺序要求相悖六、面试相关口述思路直接背这道题我用广度优先搜索 BFS 配合队列来实现。首先处理空树的边界情况根节点非空则入队。循环处理队列每一轮循环先记录当前层的节点数量然后遍历对应数量的节点逐个出队记录节点值同时将非空的左右孩子按先左后右的顺序入队。每一层处理完成后将当前层列表加入结果集最终返回分层结果。时间复杂度 O (n)每个节点入队出队各一次空间复杂度 O (n)队列最多存储最底层的所有节点。高频追问层序遍历还可以用什么方法实现也可以用深度优先搜索 DFS 递归实现递归时记录当前层级将节点值加入对应层级的列表中。但层序遍历更直观的解法还是 BFS 队列。这道题的常见变体有哪些自底向上层序遍历最后将结果集合反转即可锯齿形层序遍历偶数层将当前层列表反转二叉树的右视图每层只取最后一个节点二叉树每层的最大值每层遍历中记录最大值ArrayDeque 和 LinkedList 做队列有什么区别ArrayDeque底层是动态数组性能更好且不允许存 nullLinkedList底层是双向链表支持存 null。无特殊需求时优先使用ArrayDeque作为队列实现。七、复习速记口诀队列存节点先数每层量 出队记数值子空别入队 先左再往右一层一归档。总结二叉树层序遍历是 BFS 题型的通用母题核心逻辑非常固定队列 提前锁每层数量 按层处理。 看似多了一层 for 循环变得复杂实则只是在朴素 BFS 的基础上增加了「分层打包」的技巧最核心的「出队→访问→孩子入队」流程完全没有变化。复习时先吃透朴素版的核心流程再理解分层技巧的设计原因不要死记硬背代码。把这个模板练熟后续所有层序遍历的变体题都只需要在内层循环里做小幅修改就能快速解出。