二叉树题解——二叉树的层序遍历【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 模板之一。