二叉树的层序遍历 | 每日算法

🎧 语音讲解

开车或通勤时可听，跟着思路走一遍

速度

📋 题目描述

给你二叉树的根节点 root，返回其节点值的 层序遍历（即逐层地、从左到右访问所有节点）。

节点数目在 [0, 2000] 内，节点值在 [-1000, 1000] 范围内。

示例 1

输入：root = [3,9,20,null,null,15,7]

输出：[[3],[9,20],[15,7]]

示例 2

输入：root = [1]

输出：[[1]]

示例 3

输入：root = []

输出：[]

💭 模拟答题者思考

1. 暴力直觉：先 DFS 记录每个节点的深度，再按深度桶收集——要对每个深度排序同层顺序，还得额外保证「同层从左到右」，实现绕。

2. 重复在哪里？层序的本质是「先访问离根近的，再访问远的」——这正是 BFS：用队列把「下一批要处理的节点」按发现顺序排好，天然一层一层推进。

3. 关键技巧：不能弹一个就随便把子节点混进当前层——每轮用 size = len(q) 固定「这一层要处理几个」，处理完再开始下一层，否则深度会糊在一起。

4. 示例 1：队列先 [3] → 层 [3]；入队 9、20 → 层 [9,20]；再入队 15、7 → 层 [15,7]。

5. 每个节点入队、出队各一次，时间 O(n)；满二叉树最后一层约 n/2 节点在队列里，空间 O(n)。

🧠 变量语义（先读这三句再编码）

变量	类型	语义（三句法）
`q`	deque<TreeNode*>	定义：待扩展的节点队列，按「先进先出」保证同一层从左到右、由浅入深维护：队列中任意时刻的节点，其深度相同或相邻两层（取决于是否在轮内清空）更新：每轮弹出当前层全部节点后，把它们的孩子按左→右顺序入队
`level`	list<int>	定义：当前正在收集的这一层的节点值（从左到右）维护：本轮 `for _ in range(len(q))` 内，每弹出一个节点就追加其 `val` 更新：一轮结束后 `ans.append(level)`，再开启下一层
`ans`	list<list<int>>	定义：最终层序结果，外层下标为层号（0 为根层）维护：每处理完一层，`ans` 多一个内层数组更新：`ans.append(level)`；空树直接返回 `[]`

⌨️ 落码步骤

1. 若 root 为空，返回 []

2. 初始化 ans = []，q = deque([root])

3. 当队列非空：新建 level = []，令 size = len(q)

4. 循环 size 次：node = q.popleft()，level.append(node.val)；若 node.left / node.right 非空则依次入队

5. 将 level 追加到 ans，回到步骤 3

6. 返回 ans（DFS+深度哈希表是备选，面试标准写法是上述 BFS）

💻 代码实现

from collections import deque

class Solution:
    def levelOrder(self, root: TreeNode | None) -> list[list[int]]:
        if not root:
            return []
        ans: list[list[int]] = []
        q: deque[TreeNode] = deque([root])
        while q:
            level: list[int] = []
            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)
            ans.append(level)
        return ans

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        if (!root) return ans;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            int size = (int)q.size();
            vector<int> level;
            for (int i = 0; i < size; ++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);
            }
            ans.push_back(std::move(level));
        }
        return ans;
    }
};
// 时间 O(n)，空间 O(n)

📈 复杂度分析

时间复杂度 O(n)

空间复杂度 O(n)（队列最坏存满一层，约 n/2 个节点）

⚠️ 常见坑

❗ 不用 size = len(q) 而写成 while (!q.empty()) 只弹一个：会把下一层节点混进当前 level，输出变成一维或层界错乱。

❗ 孩子入队顺序写反（先右后左）：同层仍完整，但「从左到右」题意要求先左后右。

❗ 空树未特判：对 nullptr 仍入队会导致空指针访问；应直接返回 []。

🔍 必测边界 Case

Case 1：空树

root = [] → []

Case 2：单节点

root = [1] → [[1]]

Case 3：官方示例 1

root = [3,9,20,null,null,15,7] → [[3],[9,20],[15,7]]

Case 4：只有左孩子（链）

root = [1,2,null,3] → [[1],[2],[3]]（每层一个节点）