LeetCode 102. 二叉树的层序遍历

◎

本节目标

用队列和固定层大小逐层收集二叉树节点。

这道题把遍历与层序视角中的 BFS 队列直接写成二维结果：外层数组对应层数，内层数组保留同层从左到右的顺序。

查看 LeetCode 原题

朴素思路与瓶颈

若只不断出队并把所有值放进一个数组，会丢失层边界。即使队列在遍历中包含下一层节点，也不能让它们混进当前层。

核心不变量

每轮开始时的 levelSize 等于当前层尚在队列中的节点数。本轮恰好弹出这么多节点；它们的孩子只能追加到队尾，留给下一轮处理。因此每个 level 恰好是一层。

正确性依据

根单独入队时，第一轮准确收集第零层。若某轮队列恰好保存当前层，固定大小循环会弹出全部且仅有的当前层节点，并将下一层按从左到右顺序加入队列。归纳后所有层均被正确分组。

代码实现

C++

C++17

class Solution {
public:
    std::vector<std::vector<int>> levelOrder(TreeNode* root) {
        std::vector<std::vector<int>> answer;
        if (root == nullptr) {
            return answer;
        }

        std::queue<TreeNode*> nodes;
        nodes.push(root);
        while (!nodes.empty()) {
            int levelSize = static_cast<int>(nodes.size());
            std::vector<int> level;
            level.reserve(levelSize);
            for (int i = 0; i < levelSize; i++) {
                TreeNode* node = nodes.front();
                nodes.pop();
                level.push_back(node->val);
                if (node->left != nullptr) {
                    nodes.push(node->left);
                }
                if (node->right != nullptr) {
                    nodes.push(node->right);
                }
            }
            answer.push_back(level);
        }
        return answer;
    }
};

Python

Python 3

from collections import deque
from typing import Optional


class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> list[list[int]]:
        if root is None:
            return []

        answer: list[list[int]] = []
        nodes = deque([root])
        while nodes:
            level_size = len(nodes)
            level: list[int] = []
            for _ in range(level_size):
                node = nodes.popleft()
                level.append(node.val)
                if node.left is not None:
                    nodes.append(node.left)
                if node.right is not None:
                    nodes.append(node.right)
            answer.append(level)
        return answer

复杂度分析

每个节点入队、出队各一次，时间复杂度为 O(n)。队列最宽时可能保存一整层，额外空间为 O(w)，其中 w 是最大层宽；结果数组不计入额外空间。

易错点

• 在 for 循环条件中直接读取变化中的队列长度。
• 用一个全局数组收集值，最后已无法恢复层边界。
• 空树仍创建一层空数组。

模式迁移

需要每层的最大值、平均值、首节点或末节点时，保留固定 levelSize，只替换本轮的收集规则即可。