难度: Easy
一棵圣诞树记作根节点为 root 的二叉树，节点值为该位置装饰彩灯的颜色编号。请按照从左到右的顺序返回每一层彩灯编号，每一层的结果记录于一行。
示例 1：
输入：root = [8,17,21,18,null,null,6] 输出：[[8],[17,21],[18,6]]
提示：
节点总数 <= 1000
注意：本题与主站 102 题相同：https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
Submission
运行时间: 48 ms
内存: 15.2 MB
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
res = []
queue = deque()
queue.append(root)
while queue:
size = len(queue)
floor = []
for _ in range(size):
node = queue.popleft()
if node:
floor.append(node.val)
queue.append(node.left)
queue.append(node.right)
if floor:
res.append(floor)
return res
Explain
此题解采用了层次遍历（广度优先搜索）的方法来遍历二叉树。首先，使用一个队列来存储每一层的节点。在每一轮循环中，先记录当前队列的长度，这个长度代表了这一层的节点数量。然后，依次从队列中取出这些节点，并将它们的值加入到当前层的结果列表中。同时，如果当前节点有左或右子节点，就将这些子节点加入队列中。这样一来，队列总是包含了下一层的所有节点。当一层处理完毕后，将这一层的结果添加到最终结果列表中。重复这个过程，直到队列为空，此时所有的层都被处理完毕，算法结束。
时间复杂度: O(n)
空间复杂度: O(n)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
res = [] # 用来存储最终的层序遍历结果
queue = deque() # 使用双端队列来实现层序遍历
queue.append(root) # 首先将根节点加入队列
while queue: # 当队列非空时进行循环
size = len(queue) # 当前层的节点数
floor = [] # 用来暂存当前层的结果
for _ in range(size): # 遍历当前层的每个节点
node = queue.popleft() # 从队列中取出一个节点
if node: # 如果节点非空
floor.append(node.val) # 将节点的值加入当前层的结果中
queue.append(node.left) # 将左子节点加入队列
queue.append(node.right) # 将右子节点加入队列
if floor: # 如果当前层有结果
res.append(floor) # 将当前层的结果加入到最终结果中
return res
Explore
在我的层次遍历实现中，我并不会将空（null）节点添加到队列中。在遍历每个节点时，我会检查其左右子节点是否存在（即是否为null）。只有当子节点非空时，我才会将它们加入到队列中进行后续的层次遍历。这样做可以避免队列中充满无用的null值，同时也简化了代码逻辑和运行时的空间复杂度。
是的，我是基于队列的大小来确定何时结束一层的处理并将结果添加到最终结果列表中的。在每轮循环开始前，我会记录队列的长度，这个长度代表了当前层的节点数量。然后，我使用一个for循环来遍历这些节点，并处理它们。这种方法确保了每轮循环只处理当前层的节点，而不会混入下一层的节点。处理完这些节点后，当前层的结果就会被添加到最终结果中。
在我的方法中，如果树的根节点是null，那么算法会正确地处理这种情况。在将根节点加入队列之前，我没有显式检查根节点是否为null，但是在循环中，我会检查从队列中取出的每个节点是否为null。如果根节点为null，在第一次尝试从队列中取出节点时，会得到null，此时不会执行任何添加操作，也不会有任何结果被添加到最终的结果列表中。因此，算法会返回一个空列表，这是符合预期的结果。
是的，使用`for _ in range(size):`来迭代当前层的节点确实保证了只处理当前层的节点。因为在循环开始之前，我已经通过`size = len(queue)`捕获了当前层节点的数量，这个数量是基于队列的长度确定的。在for循环中，我严格处理这个数量的节点，这意味着不管队列中后来加入了多少新节点（即下一层的节点），它们都不会在当前的for循环中被处理。这确保了层次遍历的正确性和有序性。