难度: Medium
一棵圣诞树记作根节点为 root 的二叉树，节点值为该位置装饰彩灯的颜色编号。请按照从 左 到 右 的顺序返回每一层彩灯编号。
示例 1：
输入：root = [8,17,21,18,null,null,6] 输出：[8,17,21,18,6]
提示：
节点总数 <= 1000
Submission
运行时间: 44 ms
内存: 14.7 MB
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
from collections import deque
class Solution:
def levelOrder(self, root: TreeNode) -> List[int]:
res = []
queue = deque()
queue.append(root)
while queue:
node = queue.popleft()
if node:
res.append(node.val)
queue.append(node.left)
queue.append(node.right)
return res
Explain
本题解使用了广度优先搜索（BFS）策略来遍历二叉树。首先，将根节点加入到队列中。然后，使用一个循环，每次从队列中取出一个节点，如果该节点不为空，就将其值加入到结果列表中，并将其左右子节点（如果存在）按顺序加入到队列中。这个过程一直持续到队列为空，此时所有节点都已按层次遍历完毕。最终，结果列表包含了从左到右的层次遍历结果。
时间复杂度: 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
from collections import deque
class Solution:
def levelOrder(self, root: TreeNode) -> List[int]:
res = [] # 结果列表，存储层次遍历的节点值
queue = deque() # 使用双端队列作为队列，用于存储待访问的节点
queue.append(root) # 将根节点加入队列
while queue: # 当队列不为空时继续循环
node = queue.popleft() # 从队列中取出一个节点
if node: # 如果节点不为空
res.append(node.val) # 将节点的值加入到结果列表
queue.append(node.left) # 将左子节点加入队列
queue.append(node.right) # 将右子节点加入队列
return res # 返回结果列表
Explore
广度优先搜索（BFS）通过逐层访问节点来遍历树或图。使用队列来实现这一过程是因为队列是先进先出（FIFO）的数据结构，能够保证最先进入队列的节点（即当前层的节点）最先被处理，从而实现层次遍历。如果使用栈（后进先出，LIFO），则会先处理最近添加的节点，这样会导致深度优先搜索（DFS），而非层次遍历。
在题解中，`queue.append(root)`操作在函数开始时无条件执行，即不论根节点`root`是否为空都会被加入队列。如果根节点`root`是`None`，在后续的循环中，当尝试对这个`None`节点进行操作时，会直接跳过添加子节点的步骤，因为检查`if node`会失败（`None`评估为`False`）。因此，虽然`None`被加入队列，但不会对结果列表`res`造成影响。
结果列表`res`的层次顺序存储是通过队列的先进先出特性保证的。当一个节点从队列中取出时，它的子节点（左子节点和右子节点）按照从左到右的顺序被添加到队列尾部。这确保了在下一次迭代中，这些子节点将按照它们被添加的顺序被处理。由于每一层的节点都是按照从左到右的顺序进入队列并被处理，结果列表`res`自然按照层次顺序存储节点值。
在题解中的BFS过程中，空节点（即`None`）被添加到队列中但不会对结果列表产生影响。这是因为在从队列中取出节点并尝试访问它的值之前，会检查节点是否为空（`if node:`）。如果节点是空的，即`node`为`None`，则不会执行任何操作（不会访问值，也不会尝试添加子节点到队列）。因此，空节点在逻辑上被忽略，只有非空节点的值被添加到结果列表`res`中。