二叉树题解——二叉树的层序遍历【LeetCode】队列实现
102. 二叉树的层序遍历
一、算法逻辑（逐步通顺讲解每一步思路）
目标是从上到下、从左到右逐层返回二叉树的节点值。
✅ 1️⃣ 空树特判
-
如果
root是None，直接返回空列表[]。
✅ 2️⃣ 初始化数据结构
-
用
deque创建一个队列q并将root加入； -
用
ans存放最终结果，初始化为空列表。
✅ 3️⃣ 层序遍历主循环（BFS）
使用 while q: 表示只要队列不空，就持续处理下一层。
⬇ 每一层逻辑如下：
-
vals是当前层的节点值列表； -
for _ in range(len(q)):用来一次性处理当前层的所有节点（因为len(q)是当前层节点个数）； -
对于每个节点：
-
用
popleft()从左边弹出当前节点； -
把它的
val加入vals； -
若有左/右子节点，则加入队列，供下一层使用。
-
➕ 把本层值列表加入结果中
-
每一层处理完后，将
vals加入到ans。
✅ 4️⃣ 返回结果
-
所有层遍历完后，返回
ans即可。
二、核心点总结
这段写法与上一题思路一致，但在实现上有两个优化：
利用
deque实现队列结构，避免了列表pop(0)带来的性能损耗。
-
✅
popleft()是 O(1) 时间复杂度； -
✅
for _ in range(len(q)):能精确处理一层； -
✅ 代码结构更标准、更高效，更适合大型数据量的广度优先遍历。
class Solution:def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:if root is None:return []ans = []q = deque([root])while q:vals = []for _ in range(len(q)):node = q.popleft()vals.append(node.val)if node.left: q.append(node.left)if node.right: q.append(node.right)ans.append(vals)return ans三、时间复杂度分析
-
每个节点入队出队各一次，做一次常数操作；
时间复杂度：O(n)，
n为节点总数。
四、空间复杂度分析
-
最坏情况下，某一层可能有 n/2 个节点同时在队列中（完全二叉树）；
-
最终结果
ans也保存了所有节点值。
空间复杂度：O(n)
✅ 总结一句话
该队列版层序遍历通过 deque 优化了队列操作，是广度优先搜索在树结构上的最标准实现，在 O(n) 时间和 O(n) 空间复杂度下，稳定、高效、易读，是生产代码中常用的 BFS 模板之一。