数据结构与算法 / 系统课时

二叉树的层序遍历

二叉树的层序遍历

层序遍历按从上到下、从左到右的顺序访问二叉树。本课使用队列保存尚未处理的节点,并通过固定每轮队列长度,将普通广度优先遍历改造成可按层输出的结果。

学习目标

  • 使用队列实现二叉树层序遍历
  • 掌握按层分组时的队列长度快照
  • 计算树的层数与最大层宽

队列如何推进遍历

先将根节点入队,再反复取出队首节点,并把它的非空左、右孩子加入队尾。队列保证先进入的上层节点先被处理,因此访问顺序自然从上到下展开。

若要区分层级,必须在每轮开始时保存当前队列长度。这个长度代表本层尚未处理的节点数;本轮中新加入的孩子属于下一层,不能提前处理。

二叉树层序遍历的队列变化

主示例:按层返回节点

Python 的 collections.deque 支持 O(1)O(1) 的队首弹出。普通列表的 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

复杂度与常见错误

每个节点入队、出队各一次,时间复杂度为 O(n)O(n)。队列最多同时保存一层附近的节点,额外空间复杂度为 O(w)O(w),其中 ww 是最大层宽。

常见错误是在 for 循环中持续使用变化后的队列长度,这会把下一层混入当前层。空树还可能导致 max() 接收空序列;示例通过 default=0 返回合理结果。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

二叉树的层序遍历

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通