二叉树的层序遍历

🟡 Medium · 🏷️ 树、BFS、队列 · LeetCode#102

📖 题目

返回二叉树节点值的层序遍历结果——一层一层，每层从左到右。

输入	输出
root=[3,9,20,null,null,15,7]	[[3],[9,20],[15,7]]

🆕 新知识

list.pop(0) 删除开头元素是 O(n)（要把后面所有元素往前挪），不适合频繁做"从头部取出"这种操作。collections.deque 是双端队列，popleft() 是 O(1)：

from collections import deque
q = deque([root])
q.append(x)      # 入队，右边进
q.popleft()       # 出队，左边出，O(1)

💡 思路

前面几道树题都是 DFS（一条路走到底再回头，用递归/栈），这题要按层处理，改用 BFS（一层一层往外扩，像水波纹），需要用队列。

流程：把根节点放进队列（代表第一层）；每轮循环开始时先记录当前队列长度——这就是当前层的节点数，只处理这么多个就停，不多不少；处理时把每个节点的值记下来，同时把它的左右孩子放入队列（这些孩子属于下一层，不会跟当前层混在一起）。

关键就是 for _ in range(len(q)) 这句——固定住"只处理当前层"这个边界，新入队的孩子留到下一轮处理。

💻 代码

from collections import deque

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        q = deque([root])
        result = []
        while q:
            level = []
            for _ in range(len(q)):        # 只处理当前层
                node = q.popleft()
                level.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            result.append(level)
        return result

时间复杂度 O(n)，每个节点访问一次；空间复杂度 O(n)，队列最多同时存一层的节点。