如何用Python实现二叉树层序遍历，借助队列辅助完成BFS广度优先搜索？

本文共计869个文字，预计阅读时间需要4分钟。

层次遍历本质是+BFS，必须保证先进先出，在Python中是+list.pop(0)+，这是O(n)操作，节点越多就越明显。实际项目中见过10+级别的节点时，响应慢3+倍以上。

实操建议：

立即学习“Python免费学习笔记（深入）”；

• 固定用 from collections import deque，初始化写成 queue = deque([root])
• 每次取队首用 queue.popleft()（O(1)），不是 queue.pop(0)
• 添加子节点统一用 queue.append()，左右顺序别颠倒（左先右后才符合常规层序）

空节点不入队，但得判断 node 是否为 None

常见错误是把 None 也塞进队列，导致后续 node.left 报 AttributeError: 'NoneType' object has no attribute 'left'。

实操建议：

立即学习“Python免费学习笔记（深入）”；

• 入队前一定检查：if node.left: 再 queue.append(node.left)
• 进循环第一句就是 node = queue.popleft()，紧接着就 if not node: continue（虽然后者在正确入队逻辑下不会触发，但加了更安心）
• 如果题目要求输出含 None 的完整层（比如 LeetCode 102 的变体），那另说——但那是显式构造占位，不是把空指针当有效节点塞队列

按层分组返回时，用 len(queue) 快照当前层长度

想返回 [[3], [9, 20], [15, 7]] 这种嵌套列表？不能边遍历边 append 到同一层 list 里，否则搞不清哪几个属于当前层。

实操建议：

立即学习“Python免费学习笔记（深入）”；

• 每轮循环开始前，记下 level_size = len(queue)
• 用 for _ in range(level_size): 固定跑完这一层所有节点
• 避免用时间戳或额外标记节点——没必要，快照长度最直接、无副作用
• 注意：这个 len(queue) 是进入 for 循环前的值，之后 append 新节点不影响本轮迭代次数

递归写法看似简洁，但不是真层序遍历

有人用 DFS 加个 depth 参数，按深度把节点塞进对应下标列表里，结果输出对了，但执行顺序是深度优先的，根本没用到队列，也不满足 BFS 的访问时序要求。

实操建议：

立即学习“Python免费学习笔记（深入）”；

• 题目明确要求“广度优先”或“使用队列”，这种递归解法就算答案对，也会被判定逻辑错误
• DFS 模拟层序在极端不平衡树下内存占用反而更高（递归栈深 ≈ 节点数）
• 真要递归，至少得配合 queue 模拟，但那就绕回迭代了——没优势

事情说清了就结束。真正容易被忽略的是：队列操作的常数性能差异在小数据上看不出，但一旦节点带 payload（比如每个节点存一个大 dict），list.pop(0) 的内存搬移成本会突然暴露。