Vertical Order Traversal of a Binary Tree
二叉树按堆顺序存储在数组 root 中：根节点位于索引 0，索引 i 的子节点位于 2*i+1（左侧）和 2*i+2（右侧），-1 表示空位置，数组末尾可能还有多余的 -1 项。
根节点位于第 0 列；左子节点比其父节点向左一列，右子节点比其父节点向右一列。按从左到右的顺序，每列返回一个列表。在每列中，按从上到下的顺序列出节点；同一列、同一深度的节点按值从小到大排列。
函数
- rootinteger-array
- 按堆顺序排列的树，空位用 -1 表示
- 返回值integer-2d-array
- 每列一个值列表，先从最左侧的列开始，每列从上到下
约束条件
1 ≤ root.length ≤ 32767- 每个
root[i]都是-1，或满足0 ≤ root[i] ≤ 5000的值，并且没有重复值。 root[0]永远不会是-1，因此这棵树至少有一个节点。- 数组在最后一个节点之后可能还会有额外的
-1项。 - 空位置的两个子节点也都是空的，并且树最多有
14层。
示例
- 输入
- root = [5, 2, 9, 4, 7, 1, 6]
- 输出
- [[4], [2], [5, 1, 7], [9], [6]]
- 解释
- 第 0 列存放根节点
5，再往下两层是7和1。这两个节点的列和深度相同，因此1排在7前面，尽管7更靠左。
- 输入
- root = [1, 2, 3, -1, 4, -1, -1, -1, -1, 5]
- 输出
- [[2, 5], [1, 4], [3]]
- 解释
- 列 -1 在深度 1 处存放
2，在深度 3 处存放5（4的左子节点）。列 0 存放根节点1，以及索引 4 处的4。列 1 只存放3。
- 输入
- root = [6, -1, -1]
- 输出
- [[6]]
- 解释
6没有子节点，所以答案只有一列，即[6]。
进阶
每个值都不超过 5000。你能利用这一点去掉比较排序，并在 O(n + 5000) 时间内完成吗？
提示
逐个打开提示，每个都会多透露一点。
每个节点都有列、深度和值。如果把这些三元组都放在一个列表中，你会如何按答案的顺序排列它们？
广度优先搜索已经按从上到下的顺序输出节点。当多个节点位于同一列和同一层时，顺序中还缺少哪一部分？
每次处理树的一层。先按列排序，再按值排序，然后将每个值添加到对应列的列表中。最后，从最小的列开始，依次读取各列表。
题解
每个节点都有三个键：列、深度和值。答案是按这些键排序后的节点，每列一个列表。列和深度相同的节点按值排序，而不是按遍历时从左到右遇到的顺序排序，所以你必须对所有节点一次性排序，或者对广度优先搜索的每一层分别排序。
记录每个节点，然后排序
思路
按任意顺序访问每个节点一次，并记录三元组（列，深度，值）。向子节点移动一步，深度加 1，列向左或向右移动 1。然后按列、深度和值对三元组排序。现在，每一列的节点都排列在一起，并按要求的顺序排列。遍历排序后的列表，每当列发生变化时，就新建一个内层列表。
在示例 1 中，第 0 列的三元组排序后为 (0, 0, 5)、(0, 2, 1)、(0, 2, 7)。排序的复杂度为 O(n log n)，高于 O(n) 的遍历；三元组占用 O(n) 空间。
算法
- 将（索引 0，列 0，深度 0）压入栈中。
- 弹出一个节点，记录（列，深度，值），然后将每个实际子节点压入栈中，列为
col-1或col+1，深度为depth+1。 - 栈为空时，先按列排序，再按深度排序，最后按值排序。
- 遍历这些三元组，每当列发生变化时，就开始一个新列表。
def verticalTraversal(root):
n = len(root)
entries = [] # (column, depth, value) for every node
stack = [(0, 0, 0)] # (node index, column, depth); the root is never empty
while stack:
i, col, depth = stack.pop()
entries.append((col, depth, root[i]))
for child, child_col in ((2 * i + 1, col - 1), (2 * i + 2, col + 1)):
if child < n and root[child] != -1:
stack.append((child, child_col, depth + 1))
# Column, then depth, then value: exactly the order of the answer.
entries.sort()
result = []
for k, (col, depth, value) in enumerate(entries):
if k == 0 or col != entries[k - 1][0]:
result.append([]) # a new column starts
result[-1].append(value)
return result逐层排序
思路
广度优先搜索每次处理一层。如果每个节点在被处理时将自己的值追加到所在列的列表中，那么每个列表都已经按从上到下的顺序排列，因此不需要按深度排序。同一层中才会出现平局，因此在处理每一层之前，先按列排序，再按值排序。
在示例 1 中，第 2 层的节点按列 -2、0、0、2 的顺序到达，值为 4, 7, 1, 6，排序后变为 4, 1, 7, 6，因此第 0 列变为 [5, 1, 7]。被占用的列构成一个连续范围，因此只需记录最小列和最大列。
对包含 m 个节点的一层进行排序，时间开销为 O(m log m)。最坏情况下仍为 O(n log n)，因为满二叉树的最后一层包含大约一半的节点。空间开销为 O(n)。
算法
- 从一个包含节点（索引 0，列 0）的层级开始。
- 按列排序，然后按值排序。
- 按此顺序，将每个值添加到对应列的列表中，并将其真实子节点（列为
col-1和col+1）收集到下一层级。 - 重复此过程，直到某个层级为空，同时记录最小列和最大列。
- 从最小列到最大列依次返回这些列表。
def verticalTraversal(root):
n = len(root)
columns = {} # column -> its values, top to bottom
level = [(0, 0)] # (node index, column) of every node on the current level
while level:
# Every node here has the same depth: order them by column, then value.
level.sort(key=lambda node: (node[1], root[node[0]]))
next_level = []
for i, col in level:
columns.setdefault(col, []).append(root[i])
for child, child_col in ((2 * i + 1, col - 1), (2 * i + 2, col + 1)):
if child < n and root[child] != -1:
next_level.append((child, child_col))
level = next_level
# The columns that hold a node form one unbroken range.
return [columns[col] for col in range(min(columns), max(columns) + 1)]
易错点和边界情况
- 按从左到右的顺序保留并列值。如果不按层排序，广度优先搜索会得到示例 1 中第 0 列的
[5, 7, 1]，而不是[5, 1, 7]。 - 不排序，在深度优先遍历过程中追加值。在
[1, 2, 3, -1, 4, -1, -1, -1, -1, -1, 5]中，先遍历左侧的方式会先将5（深度为 3）追加到第 1 列，然后才追加3（深度为 1）。 - 按列和值排序，但不按深度排序。这样，示例 1 中的第 0 列会变成
[1, 5, 7]。 - 用字符串作为列的键。按文本排序时，
"-1"会排在"-2"前面，因此 0 左侧的列顺序会出错。
常见问题3
二叉树的垂直顺序遍历的时间复杂度是多少？
按列、深度和值对所有节点排序，耗时为 O(n log n)，并且其开销超过了 O(n) 的遍历。逐层排序的最坏情况也相同，因为满二叉树的最后一层大约有一半的节点。空间复杂度为 O(n)。
垂直顺序遍历可以不排序吗？
只有在平局时按从左到右的顺序排列才成立。然后，使用广度优先搜索，将每个值追加到其所在列的列表中，就能在 O(n) 时间内得到答案。如果平局时按值排序，你就需要进行一些排序，但只需在每一层内排序，因为只有同一层的节点才可能出现平局。
垂直顺序遍历与顶视图和底视图有什么关系？
这三种遍历都会按列编号对节点分组。顶部视图保留每列最浅的节点，底部视图则保留最深的节点。垂直顺序遍历会保留所有节点；如果多个节点处于同一层，则按值排序，而这两种视图会按位置选取节点。
def verticalTraversal(root):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
root = [5, 2, 9, 4, 7, 1, 6]
预期输出
[[4], [2], [5, 1, 7], [9], [6]]