题目描述
思路解析
一句话答案：LeetCode 102 二叉树的层序遍历用队列做 BFS：根先入队，每轮循环开始时记下队列当前长度，恰好出队这么多个节点组成一层，出队时把非空孩子入队。先进先出保证层内从左到右、层与层不串。每个节点入队出队各一次，时间 O(n)，空间 O(n)。
层序遍历要的输出长什么样
题目要求从根开始逐层访问二叉树，每层内部从左到右，并且结果要按层分组——返回的是「数组的数组」，第 k 个子数组装第 k 层所有节点的值。这个「分组」要求是本题的真正考点：单纯把节点按层的顺序吐出来不难，难的是准确知道每一层在哪里结束。
为什么层序遍历用队列而不是递归
深度优先的递归天生「一条道走到黑」，先扎进左子树最深处才回头，访问顺序和按层完全拧着。而层序遍历的本质是广度优先搜索（BFS）：先处理离根近的，再处理离根远的。队列的先进先出恰好维护这个次序——根先入队；每出队一个节点，就把它的左右孩子（下一层）追加到队尾。第 k 层的节点总比第 k+1 层的先进队，也就总被先处理，逐层推进不需要任何额外排序。
顺带一提，同层从左到右也是队列天然保证的：父节点按左到右出队，各自的孩子也按左到右入队，顺序全程保持。换成栈就成了后进先出，直接退化回深度优先。
怎么知道一层在哪里结束
关键技巧是在处理每一层之前，先把队列当前的长度记下来，记作 sz。此时有一个不变量成立：队列里恰好装着当前层的全部节点、且只有当前层的。于是接下来只出队 sz 个，出来的必然正好是这一层；过程中入队的孩子全属于下一层，它们排在队尾、这一轮碰不到。sz 个处理完，不变量对下一层重新成立，循环继续。
如果不先锁定 sz，直接写 while 循环边出队边入队，队列长度在循环中不断变化，就再也分不清谁是哪层的——这是本题第一大错误写法。
每个细节为什么这样写
根为空要先返回空数组，否则空树入队会立刻出错。孩子入队前必须判非空：把 null 塞进队列，下一轮出队时要么崩溃、要么污染下一层的结果。循环的终止也很自然——最底层都是叶子，没有新节点入队，队列耗空，while 结束，所有层恰好各归其位。
复杂度怎么数，还能怎么变形
时间 O(n)：每个节点恰好入队一次、出队一次，每次操作 O(1)。空间 O(n)：队列的峰值出现在最宽的一层，完全二叉树的最底层约有 n/2 个节点，量级就是 O(n)。
这套「锁层长的 BFS」是一批题的公共骨架：之字形层序（LeetCode 103）只需把偶数层的结果反转；求每层最大值、右视图等也都是在「一层一组」这个结构上做文章。骨架写熟，这些变形都是一两行的改动。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住这条：出队一个、孩子入队，队列自动帮你一层一层往下推。
根节点入队。出队一个、把它的孩子入队，队列天然按层推进。
出队 1：加入第 1 层结果。出队一个、把它的孩子入队，队列天然按层推进。
1 的孩子 2 入队。出队一个、把它的孩子入队，队列天然按层推进。
1 的孩子 3 入队。第 1 层扫完：[1]——队列里现在全是下一层节点，继续。
出队 2：加入第 2 层结果。出队一个、把它的孩子入队，队列天然按层推进。
2 的孩子 4 入队。出队一个、把它的孩子入队，队列天然按层推进。
2 的孩子 5 入队。出队一个、把它的孩子入队，队列天然按层推进。
出队 3：加入第 2 层结果。出队一个、把它的孩子入队，队列天然按层推进。
3 的孩子 6 入队。出队一个、把它的孩子入队，队列天然按层推进。
3 的孩子 7 入队。第 2 层扫完：[2, 3]——队列里现在全是下一层节点，继续。
出队 4：加入第 3 层结果。出队一个、把它的孩子入队，队列天然按层推进。
4 的孩子 8 入队。出队一个、把它的孩子入队，队列天然按层推进。
4 的孩子 9 入队。出队一个、把它的孩子入队，队列天然按层推进。
出队 5：加入第 3 层结果。出队一个、把它的孩子入队，队列天然按层推进。
5 的孩子 10 入队。出队一个、把它的孩子入队，队列天然按层推进。
5 的孩子 11 入队。出队一个、把它的孩子入队，队列天然按层推进。
出队 6：加入第 3 层结果。出队一个、把它的孩子入队，队列天然按层推进。
6 的孩子 12 入队。出队一个、把它的孩子入队，队列天然按层推进。
出队 7：加入第 3 层结果。第 3 层扫完：[4, 5, 6, 7]——队列里现在全是下一层节点，继续。
出队 8：加入第 4 层结果。出队一个、把它的孩子入队，队列天然按层推进。
出队 9：加入第 4 层结果。出队一个、把它的孩子入队，队列天然按层推进。
出队 10：加入第 4 层结果。出队一个、把它的孩子入队，队列天然按层推进。
出队 11：加入第 4 层结果。出队一个、把它的孩子入队，队列天然按层推进。
出队 12：加入第 4 层结果。第 4 层扫完：[8, 9, 10, 11, 12]——叶子层没有新节点进队，队列已经为空，循环结束。
空树、单节点、退化成链都要照顾到——逻辑不变，size 自然处理。
层序遍历的本质就是 BFS；换队列为栈就成了 DFS，方向完全不同。
参考代码
def levelOrder(root): if not root: return [] res, q = [], deque([root]) while q: level = [] for _ in range(len(q)): # 锁定本层个数 node = q.popleft() # 出队一个 level.append(node.val) if node.left: q.append(node.left) # 孩子入队 if node.right: q.append(node.right) res.append(level) return res复杂度
- 时间：O(n)，每个节点恰好入队、出队各一次
- 空间：O(n)，队列最多装下最宽一层的节点
易错点
面试追问把动画讲成自己的话
追问为什么用队列而不是栈？
追问怎么做「锯齿层序」（之字形）？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
二叉树右视图
LeetCode 199 · 中等 · 沿着 树 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题