LC102　二叉树的层序遍历¶

中等通过率 70.8%python3核心代码模式二叉树样例通过牛客 AC树广度优先搜索二叉树

一句话

一次处理一整层，本层节点的孩子按序拼出下一层。

解题思路¶

这题考什么¶

层序遍历就是广度优先搜索（BFS），难点不在「按层访问」，而在输出要按层分组：答案是嵌套列表，第 i 个子列表恰好是第 i 层的全部值。用一个队列逐个弹出的话，节点会混在一起，分不出层的边界。

分层有两种常见写法：记下本层的节点数，弹够这么多个算一层；或者干脆整层整层地换 —— 手里始终握着「当前层的全部节点」，把它们的值收成一行，再把它们的孩子按从左到右的顺序拼成下一层。这里用后者：层界由列表边界天然表达，不需要额外计数；也不需要双端队列，因为整层一起替换，从来不做「从头部弹一个」的操作。孩子的追加顺序（先左后右）直接决定了每层的从左到右，这是全部的顺序保证。层序遍历的模板见树的基础与遍历的「二叉树的三种遍历」一节。

示例 1 的 [3,9,20,null,null,15,7]：

level = [3]      -> 收 [3]，孩子拼出 [9, 20]
level = [9, 20]  -> 收 [9,20]，9 没有孩子，20 的孩子拼出 [15, 7]
level = [15, 7]  -> 收 [15,7]，两个叶子没有孩子，下一层为空，结束

输出 [[3],[9,20],[15,7]]，与样例一致。

数据规模与复杂度¶

节点数在 [0, 2000]，节点值在 [-1000, 1000]。每个节点恰好被收集一次、被展开一次，时间 O(n)；空间是最宽一层的节点数，完全二叉树下约 n/2，量级 O(n)。全程没有递归，2000 个节点排成一条链也不涉及栈深度问题。

坑在哪¶

顺序就是答案。这题在 meta.json 的 judge 里没有条目，走的是默认的严格比对，层间与层内都不允许换序。嵌套列表容易让人联想到分组类题目的「顺序无关」判定（那类题会在配置里显式标 unordered_deep），这题不是。
追加孩子必须先左后右。写反了每层就成了从右到左，示例 1 会输出 [[3],[20,9],[7,15]]。
空树返回 []，不是 [[]]。初始层是 [root]，不先判空的话第一轮就会把一个 None 收进结果并对它取 .left。题面示例 3 给的正是空树。
循环条件是「当前层非空」。下一层为空表示已经走过最深一层，此时停下；改成按总节点数计数或者预先算层数，都要额外维护，容易差一层。

参考实现¶

solutions/leetcode/LC102/sol.py
from typing import List, Optional


class Solution:
    def levelOrder(self, root: "Optional[TreeNode]") -> List[List[int]]:
        out: List[List[int]] = []
        # 空树一层都没有，返回空列表（不是含一个空层的 [[]]）
        if root is None:
            return out
        # 循环不变量：level 始终是「当前这一层」的全部节点，且已按从左到右排好
        level = [root]
        while level:
            # 本层的值收成一行，行内顺序就是 level 的顺序
            out.append([node.val for node in level])
            # 用本层节点的孩子拼下一层；先左后右决定了下一层仍是从左到右
            nxt: List["TreeNode"] = []
            for node in level:
                if node.left is not None:
                    nxt.append(node.left)
                if node.right is not None:
                    nxt.append(node.right)
            # 整层替换，层界由列表边界天然表达，不必额外计数
            level = nxt
        return out

LC102 二叉树的层序遍历¶