难度: Medium
一棵圣诞树记作根节点为 root 的二叉树，节点值为该位置装饰彩灯的颜色编号。请按照如下规则记录彩灯装饰结果：
- 第一层按照从左到右的顺序记录
- 除第一层外每一层的记录顺序均与上一层相反。即第一层为从左到右，第二层为从右到左。
示例 1：
输入：root = [8,17,21,18,null,null,6] 输出：[[8],[21,17],[18,6]]
提示：
节点总数 <= 1000
Submission
运行时间: 44 ms
内存: 15.3 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[List[int]]:
res = []
queue = deque()
queue.append(root)
while queue:
size = len(queue)
tmp = []
for _ in range(size):
node = queue.popleft()
if node:
tmp.append(node.val)
queue.append(node.left)
queue.append(node.right)
if tmp:
if len(res) % 2 == 0:
res.append(tmp)
else:
res.append(tmp[::-1])
return res
Explain
这个题解采用了广度优先搜索（BFS）的策略来遍历二叉树。使用队列来实现层序遍历，并记录每一层的节点值。在遍历过程中，每次从队列中提取当前层的所有节点，分别记录它们的值后，再将它们的左右子节点按顺序加入队列。通过一个外部列表 'res' 来存储每一层的结果。为了满足题目中的交替顺序要求，我们通过检查当前结果列表的长度来判断当前层是奇数层还是偶数层（从0开始计算），从而确定添加顺序是正常还是反转。
时间复杂度: 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[List[int]]:
res = [] # 结果列表
queue = deque() # 使用队列进行BFS
queue.append(root) # 将根节点加入队列
while queue: # 当队列不为空时
size = len(queue) # 当前层的节点数
tmp = [] # 临时列表存储当前层的结果
for _ in range(size):
node = queue.popleft() # 从队列中移除节点
if node: # 如果节点非空
tmp.append(node.val) # 将节点值加入临时列表
queue.append(node.left) # 将左子节点加入队列
queue.append(node.right) # 将右子节点加入队列
if tmp: # 如果当前层有节点
if len(res) % 2 == 0: # 根据层数决定顺序
res.append(tmp)
else:
res.append(tmp[::-1]) # 反转顺序添加
return res
Explore
在广度优先搜索（BFS）过程中，使用队列是因为它以先进先出（FIFO）的顺序处理元素，这确保了树的各层节点按照从上到下的顺序被访问。如果使用栈这样的后进先出（LIFO）数据结构，将导致节点以深度优先搜索（DFS）的顺序被处理，这不符合层序遍历的要求。尽管可以通过使用两个栈或在每层结束时反转节点来模拟层序遍历，这些方法复杂度较高，且不如直接使用队列直观有效。
题解中使用的根据奇偶层决定顺序的方法确实会在节点数较多时引入额外的处理时间，因为每遇到奇数层就要对整层节点进行一次反转操作。这个操作的时间复杂度为O(n)，其中n是该层的节点数。虽然这增加了运算量，但通常这种额外的成本是可接受的，因为这便于代码的实现和理解。如果效率成为关键问题，可以考虑在遍历过程中直接以正确的顺序插入节点值，例如使用双端队列（deque）以O(1)时间复杂度在队列头部或尾部插入节点值。
在处理节点值时，使用 append 方法是高效的，因为它的时间复杂度为O(1)。然而，使用 reverse 方法进行反转操作的时间复杂度为O(n)，可以通过其他方式优化。一种方法是使用双端队列（deque），这允许在队列的两端都可以进行O(1)时间复杂度的插入操作。这样，在需要反转顺序的层，可以通过在队列前端插入节点值来避免后续的反转操作，从而提高整体效率。