Top View of Binary Tree
你会得到一个按堆顺序存储在数组 root 中的二叉树：根节点位于索引 0，索引 i 的子节点位于 2*i+1（左侧）和 2*i+2（右侧），空位置用 -1 表示。
根节点位于第 0 列；左子节点比其父节点向左一列，右子节点比其父节点向右一列。从上方看，每列中最浅的节点；如果深度相同，则取它在该层从左到右排在最前面的节点（索引较小）。返回你看到的值，顺序从最左列到最右列。
函数
- rootinteger-array
- 按堆的顺序排列树，空位用 -1 表示
- 返回值integer-array
- 从上方看到的每列的值，从最左侧列开始
约束条件
1 ≤ root.length ≤ 32767- 每个
root[i]都是-1，或满足0 ≤ root[i] ≤ 104的值，并且没有重复值。 root[0]永远不会是-1，所以这棵树至少有一个节点。- 数组在最后一个节点之后可能还有额外的
-1项。 - 空位置的两个子节点也都是空的，并且这棵树最多有
14层。
示例
- 输入
- root = [5, 2, 9, 4, 7, 1, 6]
- 输出
- [4, 2, 5, 9, 6]
- 解释
- 从左到右，各列分别是
4（第 -2 列）、2（第 -1 列）、根节点5（第 0 列）、9（第 1 列）和6（第 2 列）。7和1也位于第 0 列，但根节点在它们上方。
- 输入
- root = [1, 2, -1, -1, 3, -1, -1, -1, -1, -1, 4]
- 输出
- [2, 1, 4]
- 解释
2在第 -1 列。它的右子节点3位于索引 4，回到了第 0 列，在根节点下方，因此被隐藏了。位于索引 10 的4是3的右子节点，单独处于第 1 列。
- 输入
- root = [6, -1, -1]
- 输出
- [6]
- 解释
- 索引 1 和 2 中存放的是
-1，所以6单独位于第 0 列，并且是整个视图。
进阶
使用节点对象而不是数组时，没有索引可以用来打破平局。你会如何说明平局规则？你的广度优先代码需要改动吗？
提示
逐个打开提示，每个都会多透露一点。
给列编号：根节点是 0，向左走一步减 1，向右走一步加 1。从上方看，你能看到某一列中的哪个节点？你如何将它与该列中的其他节点区分开来？
如果你按层访问节点，并在每一层中从左到右访问，你会先遇到某一列中的哪个节点？
对 (index, column) 对进行广度优先搜索，先添加左子节点，再添加右子节点。只有某一列第一次出现时才存储值，同时记录最小列和最大列，并在最后按顺序读取各列。
题解
每一列显示其中深度最浅的节点；如果深度相同，则显示按层序最先出现的节点。这正是广度优先搜索访问节点的顺序，因此，搜索在某一列中遇到的第一个节点就是答案。深度优先遍历也可以，但需要记录深度，并仔细处理深度相同的情况。
深度优先，每列最浅的节点
思路
按深度优先方式遍历树，同时记录每个节点的列和深度，并为每一列保留目前找到的最浅节点的深度和值。
只有在深度严格更小时才替换。两个节点深度相同时，层序遍历中靠前的节点会先被访问，因为遍历会先探索每个左子树，再探索对应的右子树，路径分叉时会先向左走。如果在深度相同时也进行替换，后访问的节点就会胜出：索引 3 为空，索引 19 和 23 处都有节点，这两个节点都在第 4 层的 -2 列，答案是索引 19 处的节点。
有节点的列构成一个连续范围，因为位于 -3 列的节点，其祖先分别位于 -1 列和 -2 列，所以要记录最小列和最大列。每个节点只访问一次，时间复杂度为 O(n)，递归深度约为 h 次调用。
算法
- 从列 0、深度 0 开始访问根节点。如果索引超出数组范围或对应的值为
-1，立即返回。 - 如果该列还没有节点，或者当前深度严格小于已存储的深度，就存储当前深度和值。
- 访问列为
col-1的2i+1，然后访问列为col+1的2i+2，深度各增加一层。 - 按列从小到大的顺序返回已存储的值。
def topView(root):
n = len(root)
best = {} # column -> (depth, value) of the shallowest node found so far
def visit(i, col, depth):
if i >= n or root[i] == -1:
return
# Replace only on a strictly smaller depth: on a tie, the node
# met first is the one further left, which comes first in level order.
if col not in best or depth < best[col][0]:
best[col] = (depth, root[i])
visit(2 * i + 1, col - 1, depth + 1)
visit(2 * i + 2, col + 1, depth + 1)
visit(0, 0, 0)
# The columns that hold a node form one unbroken range.
return [best[col][1] for col in range(min(best), max(best) + 1)]广度优先，每列的第一个节点
思路
按根节点、左子节点、再右子节点的顺序取出节点的队列，会按层序释放节点：先取出深度为 d 的所有节点，再取出深度为 d+1 的节点，并且每一层都从左向右处理。这就是题目要求的优先顺序，因此每列收到的第一个节点就是从上方看到的节点，之后的节点都会被跳过。
每个节点需要进行一次 map 查找，总时间复杂度为 O(n)。队列最多可以容纳整整一层节点，最多约占节点总数的一半，因此空间复杂度为 O(n)。
算法
- 将这对值（索引 0，列 0）放入队列。
- 取出一对值（
i，col）。如果映射中没有col对应的条目，就将root[i]存在那里。 - 对于每个存在的子节点，依次加入（
2i+1，col-1），然后加入（2i+2，col+1）。 - 队列为空时，按列从最小到最大的顺序返回映射中的值。
from collections import deque
def topView(root):
n = len(root)
top = {} # column -> value of the first node seen in that column
queue = deque([(0, 0)]) # (node index, column); the root is never empty
while queue:
i, col = queue.popleft()
# The queue hands out shallower nodes first, and left before right
# on one level, so the first node of a column is the one seen from above.
if col not in top:
top[col] = root[i]
left, right = 2 * i + 1, 2 * i + 2
if left < n and root[left] != -1:
queue.append((left, col - 1))
if right < n and root[right] != -1:
queue.append((right, col + 1))
# The columns that hold a node form one unbroken range.
return [top[col] for col in range(min(top), max(top) + 1)]
易错点和边界情况
- 采用深度优先遍历找到的第一个节点。如果根节点的左子节点有一个右子节点，且该节点还有一个右子节点（第 1 列，深度 3），遍历会先遇到它，再遇到根节点的右子节点（第 1 列，深度 1）。
- 先将右子节点加入队列：相同时会选错节点。
- 将列当作文本排序：
"-1"排在"-2"前面。 - 假设左子树填满负数列。在示例 2 中，节点
4位于根节点的左子树中，且在第 1 列。
常见问题3
二叉树的顶视图是什么？
从根节点开始将列编号为 0，左子节点的列编号减 1，右子节点的列编号加 1。顶视图会从左到右列出每一列中离根节点最近的节点。
二叉树顶视图的时间复杂度是多少？
广度优先搜索会访问每个节点一次，每个节点进行一次 O(1) 的映射查找，因此如果你跟踪最小列和最大列，运行时间为 O(n)。使用有序映射存储列时，对于 w 列，运行时间为 O(n log w)。
顶视图与左视图和底视图有什么不同？
左视图选择每一层的第一个节点。顶视图选择每一列中深度最小的节点。底视图选择每一列中深度最大的节点，因此要用广度优先搜索来查找，并覆盖每一列的节点，而不是保留第一个节点。
def topView(root):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
root = [5, 2, 9, 4, 7, 1, 6]
预期输出
[4, 2, 5, 9, 6]