二叉树的层序遍历
Binary Tree Level Order Traversal
给你一棵二叉树，按「从上到下、从左到右」的层次顺序，把每一层的节点值收集成一个数组返回。
在力扣中练习题目描述
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：[[3],[9,20],[15,7]]
示例 2：
输入：root = [1] 输出：[[1]]
示例 3：
输入：root = [] 输出：[]
提示：
- 树中节点数目在范围
[0, 2000]内 -1000 <= Node.val <= 1000
解题思路
BFS · 队列分层
队列 + 每层开始前锁住 size
深度优先会先走完一条分支，层序遍历则要求同层从左到右。队列的先进先出能保证顺序，但还需要明确每一层在哪里结束。
自拟主例 root = [8,4,12,null,6,10,15] 返回 [[8],[4,12],[6,10,15]]。4 缺少左孩子，6 是它的右孩子，图中保留这个空位。
锁定本层 sz=1；这轮只取出这 1 个节点。
- sz
- 1
每轮开始先锁定 sz = q.size()，接下来只取这 sz 个节点。处理时把孩子追加到队尾，它们属于下一层，不能改变当前循环次数。
本层结束，把 [8] 收进 res；队列中全是下一层。
本轮的 level 填完后整体追加到 res，再进入下一轮。若把不断变化的 q.size() 直接写进循环条件，同一层可能被提前截断或与下一层混合。空树不入队，结果自然为空。
易错点
- 把 sz 写成 q.size() 直接放进 for 条件里：队列在循环中会变长，循环次数就错了。
- 忘记处理空树，root 为空时访问 root->val 直接崩溃。
- 用 vector 当队列并频繁 erase(begin())，复杂度退化到 O(n²)。
DFS · 按深度归档
递归时带上 depth，把节点塞进对应层
同样是 O(n) 的正确做法，适合对照递归与按深度归档；主图解使用队列 BFS。
层序不一定非要用 BFS。带着深度递归下去，把节点放进 res[depth] 也行：
- 第一次到达某个深度时，
res.size() == depth，说明这一层还没建过，先push_back({})开一个新层； - 然后把节点值追加到
res[depth]。
因为递归是「先左后右」，同一层内的左右顺序自然就是从左到右，结果和 BFS 完全一致。
需要注意递归的访问顺序：先序遍历保证每个节点都在正确的深度被访问，且同层顺序正确。
这个写法在「二叉树的右视图」（199）里特别好用：res[depth] = node->val 覆盖写入，最后留下的就是每层最右边的节点。
- 1从根节点开始，depth = 0。
- 2若 depth == res.size()，为这一层新建一个空数组。
- 3把当前值追加到 res[depth]。
- 4递归左右孩子，depth + 1。
易错点
- 先递归再判断 depth，会导致空层被跳过。
- 用 res[depth] 直接访问而没有先扩容，会越界。
代码与演示
主解法配有图解；对照解法用于比较思路、复杂度或实现方式。
root = [8,4,12,null,6,10,15]建立结果数组和空队列；空树直接返回。
查看 C++ 代码
延伸阅读
- 「锁住当前队列长度」是 BFS 分层的通用模板，也适用于：二叉树的右视图（199）、每层最大值、之字形遍历（103）。
- 需要记录「第几层」时，BFS 用 sz 分组，DFS 用 depth 归档——两条路都能到。
- 图的 BFS（如腐烂的橘子 994）同理，只是「层」变成了「时间步」。