102. 二叉树的层序遍历 (Medium)
专题归类： 05-二叉树 LeetCode 链接： https://leetcode.cn/problems/binary-tree-level-order-traversal/
在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode
题目描述
给你二叉树的根节点 root，返回其节点值的 层序遍历。（即逐层地，从左到右访问所有节点）。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]
示例 2：
输入：root = [1]
输出：[[1]]
示例 3：
输入：root = []
输出：[]
提示：
- 树中节点数目在范围
[0, 2000]内 -1000 <= Node.val <= 1000
题目详细分析
- 数据范围含义： 节点数最多 2000，值范围 [-1000, 1000]。BFS 的队列最多存储一层的节点，最坏情况下满二叉树最后一层约 1000 个节点，内存完全 OK。
- 输入输出特征： 输入根节点，输出二维列表——每个内层列表代表一层的节点值。
- 边界条件： 空树返回
[]，单节点返回[[val]]。 - 核心约束： 分层输出，必须把同一层的节点放在同一个列表中，且保持从左到右的顺序。
- 隐藏条件： 分层是核心要求。如果只是遍历而不分层，用简单队列即可；分层需要额外技巧（记录每层节点数或用分隔符）。
小白版直白理解
就像在操场上给学生们排队点名——先叫第一排的所有人（从左到右），记下他们的名字，然后让他们报出自己后面一排的人，再叫第二排，以此类推。层序遍历就是：从根节点（第一排）开始，逐排处理，每排从左到右。
解题思路
思路一：BFS 标准模板（推荐）
核心思想： 使用队列，每次处理一整层的节点。关键技巧是 for _ in range(len(q))：在处理每层开始时，队列中的节点数就是该层的节点数。通过这个长度控制循环次数，保证不会混到下一层。
为什么 BFS 适合层序？ BFS 天然是按「层」为单位推进的——先访问所有距离为 1 的节点，再访问所有距离为 2 的节点。队列 FIFO 的特性保证了先入队的上层节点先被处理。
from collections import deque
def levelOrder(root):
if not root:
return []
res = []
q = deque([root])
while q:
level = [] # 当前层的节点值列表
level_size = len(q) # 当前层的节点数（关键！）
for _ in range(level_size):
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思路二：DFS 递归（前序 + depth 参数）
核心思想： 用深度 depth 参数记录当前节点所在的层数。递归时始终保持 res[depth] 存在对应的列表。前序遍历（根→左→右）天然保证每层从左到右的顺序。
为什么 DFS 也能做层序？ DFS 虽然是一条路走到黑，但通过 depth 参数可以知道每个节点属于哪一层，将它们放入对应的「层桶」中。但需要注意：必须先保证 res 的长度足够容纳当前层。
def levelOrder(root):
res = []
def dfs(node, depth):
if not node:
return
# 如果当前层还没有列表，新建一个
if depth == len(res):
res.append([])
res[depth].append(node.val) # 放入对应层的列表中
dfs(node.left, depth + 1) # 递归左子树
dfs(node.right, depth + 1) # 递归右子树
dfs(root, 0)
return res易错点
- BFS 中
len(q)必须在for循环前固定： 如果在 for 循环中动态取len(q)，由于循环中会 popleft 和 append，长度会不断变化。必须在一开始就把长度存到变量中。 - DFS 中
res的初始化顺序： 当第一次进入第 depth 层时，必须先res.append([])，然后再赋值。如果 res 的长度 <= depth，说明这一层还没创建。 - 空树返回
[]而不是[[]]： 空树没有节点，所以返回空列表而不是包含一个空列表。 - BFS 不要用列表模拟队列（pop(0) 是 O(n)）： 一定要用
collections.deque，它的popleft()是 O(1)。
框架提炼
BFS 层序遍历模板（必记）：
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变体思路： 将 for _ in range(len(q)) 改为 for i in range(len(q)) 可以在循环中知道当前节点在层中的位置（如右视图问题中判断 i == len(q)-1）。
关联题目
- 199-二叉树的右视图 — BFS 层序的变体，每层只取最右边（最后一个）节点。
- 107-二叉树的层序遍历 II — 同样是层序，最后将结果列表反转即可（自底向上）。
- 103-二叉树的锯齿形层序遍历 — BFS 层序 + 奇偶层反转标志位。
- 104-二叉树的最大深度 — BFS 统计层数即为最大深度。