Binary Tree Zigzag Level Order Traversal
你会得到一个以数组形式存储的二叉树 root。根节点位于索引 0，索引 i 的子节点位于 2*i+1（左侧）和 2*i+2（右侧），-1 表示空位置，数组末尾可能还有多余的 -1 项。
按层以锯齿顺序返回节点值：根节点所在层从左到右，下一层从右到左，依此交替，直到最深的一层。这也称为螺旋层序遍历。
函数
- rootinteger-array
- 按堆顺序排列的树，空位置用 -1 表示
- 返回值integer-2d-array
- 每个层级对应一个值列表，先从顶层开始，方向交替为从左到右和从右到左
约束条件
1 ≤ root.length ≤ 32767- 每个
root[i]都是-1，或者是满足0 ≤ root[i] ≤ 104的值。 - 节点值各不相同。
root[0]永远不会是-1，所以这棵树至少有一个节点。- 数组可能会在最后一个节点之后包含额外的
-1项。 - 空位置的两个子节点也都是空的，并且这棵树最多有
14层。
示例
- 输入
- root = [8, 12, 5, 1, 9, -1, 14, -1, -1, 4, 2, -1, -1, 11]
- 输出
- [[8], [5, 12], [1, 9, 14], [11, 2, 4]]
- 解释
- 从左向右读取，各层级为
8；12, 5；1, 9, 14；4, 2, 11。第 1 层和第 3 层的顺序相反：[5, 12]和[11, 2, 4]。
- 输入
- root = [1, 2, 3, 4, 5, 6, 7, -1, -1]
- 输出
- [[1], [3, 2], [4, 5, 6, 7]]
- 解释
- 一个包含三层的完整树：中间层翻转为
[3, 2]，第三层又从左向右排列。末尾的两个-1条目表示4的空子节点位置。
- 输入
- root = [5]
- 输出
- [[5]]
- 解释
- 单个节点是一层中的一个值，可以从任一方向读取。
进阶
你能把每个值直接放到所在行的最终位置，而不进行反转，也不使用第二个栈吗？
提示
逐个打开提示，每个都会多透露一点。
先按普通的层序遍历，从左到右收集各层。哪些列表需要改变，以及如何改变？
从根节点开始，将层级从 0 编号。奇数层要反向读取。反转列表的成本和读取列表一样，因此反转这些层可以让整体保持线性复杂度。
要跳过反转步骤，可以将当前层保存在一个栈中，并在弹出节点时将子节点压入另一个栈：从左向右读取时先压入左子节点，从右向左读取时先压入右子节点。这样，弹出第二个栈时，下一层的顺序就是你需要的顺序。
题解
这些层级来自普通的广度优先搜索。新增的部分是方向：每隔一层就会反转。你可以在构建完奇数行后将其反转，也可以把每一层放入栈中，这样取出项目时，顺序就会与压入时相反。
按层级顺序遍历，然后反转每隔一层
思路
队列每轮处理一层，会从左到右输出每一层的节点。从根节点开始，将层号从 0 开始编号：之字形遍历会从右到左读取奇数层，因此只需反转这些层，就能得到答案。
搜索会访问每个节点一次，每次反转还会再处理每个值一次，因此时间复杂度为 O(n)。
算法
- 从索引
0开始建立一个队列。 - 每一轮先保存队列的长度
s，将s个索引出队并放入新的一行，然后将每个索引已有的子节点入队，先左后右。 - 如果答案中已有奇数行，就反转这一行。
- 添加这一行，然后继续，直到队列为空。
from collections import deque
def zigzagLevelOrder(root):
n = len(root)
levels = []
queue = deque([0]) # node indexes; the root is never empty
while queue:
row = []
for _ in range(len(queue)): # exactly the nodes of the current level
i = queue.popleft()
row.append(root[i])
for child in (2 * i + 1, 2 * i + 2):
if child < n and root[child] != -1:
queue.append(child)
if len(levels) % 2 == 1: # levels 1, 3, 5, ... read from right to left
row.reverse()
levels.append(row)
return levels两个栈
思路
把当前层保存在一个栈中，按读取当前层的方向弹出节点，并将每个弹出节点的子节点压入第二个栈。当前栈清空时，第二个栈中就保存着下一层。
压入顺序决定了它能否正常工作。从左向右弹出时，先压入每个节点的左子节点，再压入右子节点：最右侧节点的右子节点最后压入，因此下一层会从右端开始弹出。从右向左弹出时，先压入右子节点，再压入左子节点，这样最左侧节点的左子节点最后压入。
示例 1：弹出 8，压入 12, 5。弹出 5, 12，然后将 5 的子节点 14 和 12 的子节点 9, 1 压入。弹出 1, 9, 14，然后将 9 的子节点 4, 2 和 14 的子节点 11 压入。弹出 11, 2, 4。
每个节点只压入和弹出一次：时间复杂度为 O(n)，无需反转遍历结果。
算法
- 将根节点的索引
0压入栈中，然后从左向右开始读取。 - 只要栈不为空，就将所有索引弹出并放入新的一行，然后将每个弹出节点已有的子节点压入第二个栈：从左向右读取时先左后右，否则先右后左。
- 将这一行添加到答案中。
- 将第二个栈设为当前栈，切换方向并重复。
def zigzagLevelOrder(root):
n = len(root)
levels = []
current = [0] # a stack of node indexes; the root is never empty
left_to_right = True
while current:
row = []
upcoming = [] # the next level, pushed while this one pops
while current:
i = current.pop()
row.append(root[i])
# Push so that the next level pops out in its own direction.
if left_to_right:
children = (2 * i + 1, 2 * i + 2)
else:
children = (2 * i + 2, 2 * i + 1)
for child in children:
if child < n and root[child] != -1:
upcoming.append(child)
levels.append(row)
current = upcoming
left_to_right = not left_to_right
return levels
易错点和边界情况
- 改变子节点进入同一个队列的顺序。兄弟节点交换顺序，但父节点顺序不变：示例 1 的第三层会得到
[9, 1, 14]。 - 从 1 开始计数层数。每次翻转都会错一层，示例 1 会得到
[[8], [12, 5], [14, 9, 1], [4, 2, 11]]。 - 在双栈版本中，每一层都使用相同的入栈顺序。这样，示例 1 的第三层出栈顺序会是
[9, 1, 14]。 - 把子节点压入你仍在弹出的那个栈。它们会在父节点所在层的其余节点之前弹出。
- 对一行进行排序，而不是反转它。示例 1 的最后一层必须是
[11, 2, 4]，排序无法得到这个结果。
常见问题3
锯齿形遍历和层序遍历有什么区别？
它们会按相同的节点访问相同的层。层序遍历会从左到右读取每一层；之字形遍历会从右到左读取每隔一层，从根节点下方的一层开始。两者的运行时间都是 O(n)。
锯齿形遍历和树的螺旋顺序遍历是一样的吗？
是的，这两个名称描述的是同一种遍历方式。有些文本从左侧而不是右侧开始遍历第二层，这只会让翻转操作移动一层。这里，根节点所在层从左向右，下一层从右向左。
可以用双端队列实现锯齿形层序遍历吗？
是的。按从左到右的顺序将每一层保存在双端队列中。在从左到右的一层中，从队首取出节点，并按先左后右的顺序将它们的子节点添加到队尾。在从右到左的一层中，从队尾取出节点，并按先右后左的顺序将它们的子节点添加到队首。每轮开始时记录的取出数量仍然用于界定这一层。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def zigzagLevelOrder(root):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
root = [8, 12, 5, 1, 9, -1, 14, -1, -1, 4, 2, -1, -1, 11]
预期输出
[[8], [5, 12], [1, 9, 14], [11, 2, 4]]