实现二叉树的层序遍历。

核心回答

层序遍历用队列做广度优先搜索，按从上到下、每层从左到右的顺序访问节点。 根节点先入队，每次从队首取出节点，再依次把非空左孩子、右孩子加入队尾。

如果结果需要按层分组，每轮先记录当前队列长度，只处理这么多个节点；本轮加入的孩子留到下一轮。空树返回空列表。每个节点入队、出队各一次，时间复杂度为 O(n)；辅助队列占 O(w)，w 为最大层宽，保存全部结果另需 O(n)。

Python 实现

下面返回按层分组的节点值，使用 Python 3.10 及以上版本。

from __future__ import annotations

from collections import deque
from dataclasses import dataclass


@dataclass
class TreeNode:
    val: int
    left: TreeNode | None = None
    right: TreeNode | None = None


def level_order(root: TreeNode | None) -> list[list[int]]:
    if root is None:
        return []

    queue = deque([root])
    levels = []
    while queue:
        level_size = len(queue)
        values = []
        for _ in range(level_size):
            node = queue.popleft()
            values.append(node.val)
            if node.left is not None:
                queue.append(node.left)
            if node.right is not None:
                queue.append(node.right)
        levels.append(values)
    return levels


root = TreeNode(1, TreeNode(2, right=TreeNode(4)), TreeNode(3))
assert level_order(root) == [[1], [2, 3], [4]]
assert level_order(None) == []

为什么先记录本层长度

在例子中，队列按以下过程变化，队首写在左边：

• 第一轮开始：[1]，本层只有一个节点。处理 1 后，队列变成 [2, 3]，得到第一层 [1]。
• 第二轮开始：[2, 3]，固定本层长度为 2。处理 2 后加入 4，队列是 [3, 4]；接着只处理 3，将 4 留给下一轮，得到 [2, 3]。
• 第三轮开始：[4]，得到 [4]，队列清空。

因此，外层循环开始时队列保存当前层；内层执行期间可能混有当前层剩余节点与下一层节点。如果内层一直处理到队列为空，刚加入的孩子也会被算进当前层，分层就丢失了。

左孩子先入队保证同一父节点的孩子从左到右访问；父节点本身按从左到右出队，又保证不同父节点的孩子保持正确顺序。

复杂度与边界

每个节点只处理一次，每条父子边只检查一次，所以总时间为 O(n)。Python 的 deque.append 和 popleft 适合队列两端操作；若用列表反复 pop(0)，移动剩余元素可能使总开销在宽树上达到 O(n²)。

队列会短暂混合相邻两层，空间与最大层宽同阶，为 O(w)，最坏 O(n)。单链树只有一个待处理节点，但返回结果仍包含全部 n 个值，因此不能把总空间也写成 O(1)。

实现要覆盖空树、单节点、只有一侧孩子、不满二叉树、重复值和零值。是否存在节点应检查节点引用，而不是用 node.val 的真假判断。输入按正常二叉树处理，孩子关系没有环且每个非根节点只有一个父节点。

常见追问

只需要一维访问序列呢？ 出队时直接把值加入同一个结果列表，不必记录每层长度。若已经得到分层结果，也可以按层展开。

能用 DFS 返回相同分层结果吗？ 可以在递归时携带深度，将值加入对应深度的列表，并先遍历左子树再遍历右子树。这样能得到分层输出，但实际访问过程仍是 DFS，递归栈占 O(h)，h 为树高；层数很深时还需考虑递归深度。

遍历一般图还可以不判重吗？ 树的孩子关系中不会重复到达同一节点；一般图可能有环或多条路径，通常要在节点入队时标记已发现，避免重复入队。

参考资料