Binary Tree Level Order Traversal
数组 tree 存储一棵二叉树。根节点位于索引 0 处，索引 i 处节点的子节点分别位于 2*i+1（左侧）和 2*i+2（右侧），-1 表示空位置，末尾可能还有多余的 -1 项。
按层返回节点值：每层一个列表，从根节点向下直到最深层，每层的值按从左到右的顺序排列。
函数
- treeinteger-array
- 按堆序排列的树，空位用 -1 表示
- 返回值integer-2d-array
- 每个层级对应一个值列表，先顶层，再从左到右依次排列
约束条件
1 ≤ tree.length ≤ 32767- 每个
tree[i]都是-1，或是满足0 ≤ tree[i] ≤ 1000的值。 tree[0]永远不会是-1，因此这棵树至少有一个节点。- 数组末尾在最后一个节点之后可能还有额外的
-1项。 - 空位置的两个子节点也都是空的，并且深度最多为
14。
示例
- 输入
- tree = [4, 9, 2, -1, 6, 8, 5, -1, -1, 3]
- 输出
- [[4], [9, 2], [6, 8, 5], [3]]
- 解释
- 索引 3 为空，所以
9只有一个右子节点6。第三层是6、8、5，位于索引 9、在6下方的3独自处于第四层。
- 输入
- tree = [7, -1, -1]
- 输出
- [[7]]
- 解释
- 根节点的两个子节点都是
-1，所以这棵树只有一个节点7，并且只有一层。
- 输入
- tree = [1, 3, -1, 5, -1, -1, -1]
- 输出
- [[1], [3], [5]]
- 解释
- 每个节点都只有一个左子节点：索引 1 处的
3和索引 3 处的5。每一层都只有一个值，末尾的-1项没有增加任何内容。
进阶
你能按之字形顺序返回各层吗？第一层从左到右，第二层从右到左，以此类推，不对任何一层排序。
提示
逐个打开提示，每个都会多透露一点。
索引
i的子节点位于2*i+1和2*i+2处。如果你总是先访问离根节点最近的节点，并按从左到右的顺序访问它们，你会按什么顺序遇到这些节点？队列会按照你放入节点的顺序返回节点。如果你在取出一个节点时添加它的子节点，节点就会一层一层地取出。剩下的问题是如何判断一层何时结束、下一层何时开始。
每一轮开始时，队列中恰好有一个层级。读取它的大小
s，取出s个节点放入一个新列表，然后依次添加它们的子节点，先左侧子节点，跳过-1和超出末尾的索引。队列为空时停止。
题解
每一层都必须单独按从左到右的顺序输出。使用队列进行广度优先搜索会按这个顺序访问节点，而且每轮开始时，队列中恰好包含一层的节点，因此队列的大小就是要处理的节点数。跟踪每个节点深度的深度优先遍历也可以实现。
按深度优先，按深度归档
思路
按深度优先的顺序遍历这棵树，为每个节点传入它的深度，根节点的深度为 0，并为每个深度维护一个列表。深度为 d 的节点会将其值追加到列表 d 中；如果这是该层遇到的第一个节点，就先创建这个列表。
每个列表中的节点都按从左到右的顺序排列，因为遍历会先完成节点的左子树，再进入右子树。在同一层的两个节点中，当它们的路径分开时，路径向左转的那个节点会先被访问。在示例 1 中，访问顺序 4, 9, 6, 3, 2, 8, 5 会生成 [4]、[9, 2]、[6, 8, 5]、[3]。
每个节点只访问一次：时间复杂度为 O(n)，递归深度与树的深度相同，最多 14 层。
算法
- 创建一个空的层级列表。
- 以深度 0 访问根节点。
- 在深度为
d的节点i处，如果i超出末尾，或者tree[i]为-1，就停止。 - 如果列表数量只有
d个，就添加一个空列表。将tree[i]追加到第d个列表中。 - 先以深度
d+1访问2i+1，再访问2i+2。
def levelOrder(tree):
n = len(tree)
levels = []
def visit(i, depth):
if i >= n or tree[i] == -1:
return
if depth == len(levels): # the first node seen on this level
levels.append([])
levels[depth].append(tree[i])
# Left before right, so every level fills from left to right.
visit(2 * i + 1, depth + 1)
visit(2 * i + 2, depth + 1)
visit(0, 0)
return levels广度优先，每轮遍历一层
思路
从队列中取出一个节点，并把它的子节点放入队列，先放左边的。只有当第 d 层离开时，第 d+1 层才会进入队列，因此节点会按层从左到右离开。
要把这串节点分成各层，可以在每轮开始时读取队列的大小。上一层已经离开，下一层还没有进入，因此队列中恰好是当前层的节点。取出这么多个节点作为一行，它们的子节点留到下一轮处理。在示例 1 中，每轮分别取出 1、2、3 和 1 个节点。
每个节点只进入和离开队列一次：时间复杂度为 O(n)。队列大约容纳一层的节点；在一棵满的 14 层树中，最深一层最多有 8,192 个节点。
算法
- 将根节点的索引
0放入队列。 - 当队列不为空时，读取队列的大小
s，并创建一个空行。 - 取出
s个索引。对于每个索引i，将tree[i]添加到该行。 - 如果索引在数组范围内且对应的值不是
-1，则将2i+1和2i+2依次加入队列。 - 将该行添加到答案中，并开始下一轮。
from collections import deque
def levelOrder(tree):
n = len(tree)
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(tree[i])
for child in (2 * i + 1, 2 * i + 2):
if child < n and tree[child] != -1:
queue.append(child)
levels.append(row)
return levels
易错点和边界情况
- 清空队列时读取队列的大小。在
while (j < queue.length)中，随着子节点到达，队列长度会增加，因此下一层的节点会混入当前行。 - 先添加右子节点，再添加左子节点，或者先遍历右子树。这样一来，示例 1 的第二层会变成
[2, 9]。 - 跳过边界检查
child < n。最深层节点的子节点会超出数组末尾。 - 从普通数组列表的开头移除元素，这在许多语言中会导致每次都移动整个队列。请使用真正的队列或头部索引。
- 把
-1当作节点。它不会进入任何一行或队列：[7, -1, -1]会得到[[7]]，而不是[[7], []]。
常见问题3
二叉树层序遍历的时间复杂度是多少？
两种答案都会访问每个节点一次：对于 n 个节点，时间复杂度为 O(n)。答案中包含 n 个值，因此空间复杂度为 O(n)。此外，队列最多存储最宽层的节点，递归的深度则等于树的高度。
在广度优先搜索中，你如何知道一个层级在哪里结束？
在每一轮开始时读取队列的大小，并且只取这么多个节点。还有两种方法也可行：用两个单独的列表分别保存当前层和下一层，或者在每一层结束后向队列中放入一个标记。
数组已经按层存储好了。为什么不按切片读取它呢？
对于这种格式，它适用：层级 d，根节点位于 0，填充索引 2^d-1 到 2^(d+1)-2，因此要收集每个范围内的非空值，直到某个范围内没有值。面试中通常会传入带有指针的节点对象，这种形式中只有队列仍然适用。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def levelOrder(tree):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
tree = [4, 9, 2, -1, 6, 8, 5, -1, -1, 3]
预期输出
[[4], [9, 2], [6, 8, 5], [3]]