二叉树的层序遍历怎么做？如何按层分组输出？

简化版

层序遍历就是广度优先（BFS），用一个队列：根节点入队，然后循环「出队一个节点、访问它、把它的左右孩子入队」，直到队空。想按层分组，就在每轮循环开始时记录当前队列大小 size，一次处理 size 个节点，正好是一整层。

详细版

List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    if (root == null) return res;
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    while (!q.isEmpty()) {
        int size = q.size();                 // 关键：先记住本层节点数
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < size; i++) {     // 只处理这一层
            TreeNode node = q.poll();
            level.add(node.val);
            if (node.left  != null) q.offer(node.left);
            if (node.right != null) q.offer(node.right);
        }
        res.add(level);                      // 一层收集完
    }
    return res;
}

核心技巧：进入每层循环前先固定 size = q.size()。因为循环体里会往队列加下一层的节点，如果不固定 size，就分不清「本层」和「下一层」的边界。

完整版教学

一、为什么用队列

层序遍历要求「上层先于下层、同层从左到右」被访问。也就是先入队的节点，它的孩子也要先被处理——这正是先进先出（FIFO），所以用队列。根入队后，每次从队头取一个节点处理，并把它的孩子加到队尾，队列里始终是「即将访问的、按层排好序的」节点。

二、按层分组的关键：固定 size

不分组的层序很简单，但面试常要求每层单独成一个列表。难点是：处理本层节点时，会把下一层的孩子也加进同一个队列，怎么知道「本层到哪结束」？

答案是在处理本层前，先把队列当前大小存到 size——这时队列里恰好是完整的一层。然后只循环 size 次，处理的就正好是这一层，期间新加入的孩子属于下一层、留到下一轮。这个「先量一层的长度」是 BFS 分层的通用套路。

三、常见变体，全靠这个框架

锯齿形（之字形）层序：奇数层从左到右、偶数层从右到左。只需用一个布尔位控制每层是正着加还是反着加（或每层收集后按需反转）。
二叉树的右视图：每层最后一个节点（i == size-1 时记录）。
每层的最大值 / 平均值：处理每层时顺带求 max / 求和。
二叉树的最小深度：BFS 遇到的第一个叶子节点所在层就是最小深度（比 DFS 更快，找到即停）。
判断完全二叉树：层序遍历，遇到空节点后若还有非空节点，则不是完全二叉树。

掌握「队列 + 固定 size 分层」这一个框架，这些题都是它的变体。

四、复杂度

时间 O(n)：每个节点入队、出队各一次。
空间 O(w)：队列最多同时装下最宽一层的节点数 w，最坏（满二叉树最后一层）约为 n/2，即 O(n)。

五、层序 vs 深度优先求深度

求树的深度，DFS 和 BFS 都能做。但求最小深度时 BFS 更优：BFS 一层层往下，遇到的第一个叶子节点立刻就是答案，可以提前返回；而 DFS 得把所有路径都探完才能确定最小值。这是 BFS「按层推进」特性的一个实用优势。

六、常见误区与追问

变体	在固定 `size` 循环里的处理
右视图	记录本层 `i == size - 1` 的节点
每层平均值	本层累加求和，循环结束除以 `size`
锯齿层序	按层号决定本层结果是否反转或头插
最小深度	遇到第一个叶子节点立即返回当前层数

记忆钩子：层序遍历的「层」不是节点自己知道的，而是进入这一层前队列里已有的那一批节点。

误区：循环里直接用动态变化的 q.size() 控制本层。 遍历当前层时会不断加入下一层节点，必须先把本层大小固定下来。
误区：层序遍历只能输出一维列表。 只要固定每层 size，就能自然得到二维分层结果，也是右视图、平均值、锯齿遍历的基础。
误区：BFS 空间一定比 DFS 小。 满二叉树最宽一层约 n/2 个节点，队列最坏是 O(n)；DFS 在平衡树上通常是 O(log n)。
追问：为什么最小深度适合 BFS？ BFS 按层推进，第一次遇到叶子节点时，它一定处在最浅层，可以立即返回。
追问：如果要从右到左层序怎么办？ 入队顺序或本层结果收集顺序可以调整，但仍然要保持队列按层推进。
追问：空树返回什么？ 返回空列表或深度 0，取决于题目返回类型；核心是先处理 root == null。

七、加强记忆

层序遍历 = BFS，用队列：根入队，循环「出队访问、左右孩子入队」到队空。按层分组的关键是进入每层前先固定 size = q.size()，只处理这么多个就是一整层。之字形、右视图、每层最值、最小深度、判断完全二叉树都是这个框架的变体。时间 O(n)、空间 O(w)。求最小深度用 BFS 可提前返回。

简化版

详细版