二叉树的层序遍历 图解题解

层序遍历要的输出长什么样

题目要求从根开始逐层访问二叉树，每层内部从左到右，并且结果要按层分组——返回的是「数组的数组」，第 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）只需把偶数层的结果反转；求每层最大值、右视图等也都是在「一层一组」这个结构上做文章。骨架写熟，这些变形都是一两行的改动。

Python

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

Java

public 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 sz = q.size();            // 锁定本层个数
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < sz; 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;
}

C++

vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> res;
    if (!root) return res;
    queue<TreeNode*> q; q.push(root);
    while (!q.empty()) {
        int sz = q.size();            // 锁定本层个数
        vector<int> level;
        for (int i = 0; i < sz; ++i) {
            TreeNode* node = q.front(); q.pop();  // 出队一个
            level.push_back(node->val);
            if (node->left)  q.push(node->left);   // 孩子入队
            if (node->right) q.push(node->right);
        }
        res.push_back(level);
    }
    return res;
}