题目

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
示例 1：

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

示例 2：
输入：root = [1]
输出：[[1]]

示例 3：
输入：root = []
输出：[]

题目链接

我的思路

用队列实现（因为队列有先入先出的特点）

1. 处理极值
2. 定义一个双向队列（collections.deque()）和结果数组res
3. 将根节点插入队列
4. 定义循环，当队列不为空时循环继续
   • 每次循环弹出一个节点，记录节点的值到数组res
   • 判断左子树和右子树是否存在，如果存在则加入队列
5. 返回结果

思路不足：

• 没有考虑每层的值应该放在一个数组里

题解思路

• 新建一个临时列表 tmp ，用于存储当前层打印结果
• 用两层循环而不是一层，内层循环遍历并弹出当前队列里所有的元素，值加入tmp数组
• 内层循环结束后tmp数组加入res数组

参考代码

python"># Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = rightfrom collections import deque
class Solution:def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:# 0.处理极端情况if root is None:return []deq = deque()res = []# 1.根入栈deq.append(root)# 2.循环，栈不为空while deq:tmp = []for _ in range(len(deq)):# 3.出栈，获取出栈元素的值node = deq.popleft()tmp.append(node.val)# 4.左子树入栈if node.left is not None:deq.append(node.left)# 5.右子树入栈if node.right is not None:deq.append(node.right)res.append(tmp)return res

Q&A

1. 为什么for _ in range(len(deq))不会报错，for _ in deq会报错？
   在Python中，for _ in range(len(deq)) 和 for _ in deq 表面上看起来似乎做同样的事情，但实际上它们在处理队列（deque）时的行为是不同的。

   • for _ in range(len(deq))： 首先计算队列的长度，即 len(deq)，然后循环这个固定的次数。在循环过程中，即使队列 deq 的长度发生了变化（元素添加或移除），循环的次数也不会改变，因为它在循环开始时就已经确定了。因此，这个循环不会因为队列的变化而报错。
   • for _ in deq：这个循环直接迭代队列中的元素。如果在迭代过程中队列被修改，迭代器会检测到这种变化，并抛出 RuntimeError: deque mutated during iteration 错误。这是因为Python的迭代器协议要求在迭代过程中，被迭代的对象应该是不可变的，以保证迭代器的状态和对象的状态保持一致

2. 为什么左子树和右子树的插入要放在内层循环？
   如果在内层循环之外添加子节点，会在处理当前层的所有节点之前就将子节点添加到队列中，这可能导致某些节点被遗漏或者遍历顺序不正确
   例如：