数据结构与算法 / 系统课时
二叉树的层序遍历
二叉树的层序遍历
层序遍历按从上到下、从左到右的顺序访问二叉树。本课使用队列保存尚未处理的节点,并通过固定每轮队列长度,将普通广度优先遍历改造成可按层输出的结果。
学习目标
- 使用队列实现二叉树层序遍历
- 掌握按层分组时的队列长度快照
- 计算树的层数与最大层宽
队列如何推进遍历
先将根节点入队,再反复取出队首节点,并把它的非空左、右孩子加入队尾。队列保证先进入的上层节点先被处理,因此访问顺序自然从上到下展开。
若要区分层级,必须在每轮开始时保存当前队列长度。这个长度代表本层尚未处理的节点数;本轮中新加入的孩子属于下一层,不能提前处理。

主示例:按层返回节点
Python 的 collections.deque 支持 的队首弹出。普通列表的 pop(0) 需要移动后续元素,节点较多时会带来额外开销。
python
from collections import deque
class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def level_order(root):
if root is None:
return []
queue = deque([root])
levels = []
while queue:
# 固定本层节点数,避免把新入队的下一层提前处理
level_size = len(queue)
current_level = []
for _ in range(level_size):
node = queue.popleft()
current_level.append(node.value)
if node.left is not None:
queue.append(node.left)
if node.right is not None:
queue.append(node.right)
levels.append(current_level)
return levels
root = Node(
"A",
Node("B", Node("D"), Node("E")),
Node("C", None, Node("F")),
)
levels = level_order(root)
print("层序结果:", levels)
print("树的层数:", len(levels))
print("最大层宽:", max(map(len, levels), default=0))预期输出
text
层序结果: [['A'], ['B', 'C'], ['D', 'E', 'F']]
树的层数: 3
最大层宽: 3复杂度与常见错误
每个节点入队、出队各一次,时间复杂度为 。队列最多同时保存一层附近的节点,额外空间复杂度为 ,其中 是最大层宽。
常见错误是在 for 循环中持续使用变化后的队列长度,这会把下一层混入当前层。空树还可能导致 max() 接收空序列;示例通过 default=0 返回合理结果。
按自己的节奏,确认真正理解。