Binary Tree Right Side View
数组 root 存储一棵二叉树。根节点位于索引 0 处，索引为 i 的节点，其子节点分别位于 2*i+1（左侧）和 2*i+2（右侧），-1 表示空位置，末尾可能还有多余的 -1 条目。
从右侧观察这棵树。每一层你只能看到一个节点，就是最右侧的那个节点，其余节点都被挡住了。从根节点所在层开始，到最深的一层为止，按顺序列出这些节点的值。
函数
- 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, 7, 4, -1, 1, -1, 3]
- 输出
- [5, 9, 1, 3]
- 解释
- 从右侧可以看到
5、9和1（索引 6）。第四层只有3，它位于左子树中7下方的索引 8 处。右侧没有节点到达那么深，所以可以看到3。
- 输入
- root = [6, 0, -1, 8, -1, -1, -1]
- 输出
- [6, 0, 8]
- 解释
- 这棵树是一条由左子节点组成的链：
6、0、8。每一层都只有一个节点，所以你能看到这三个节点，尽管它们都不是右子节点。
- 输入
- root = [42]
- 输出
- [42]
- 解释
- 长度为 1 的数组：根节点
42完全没有子节点位置，视图中只有这一个值。
进阶
如何获取一棵树的右视图？树中的每个节点可以有任意数量的子节点，并按从左到右的顺序存储在列表中。
提示
逐个打开提示，每个都会多透露一点。
沿着示例 1 的右侧子节点向下走，会得到
5, 9, 1，然后停止。答案里还有第四个值。它是从哪里来的？按深度而不是按左右分组节点。将每一层从左到右写出来：在这个列表中，右侧的人会看到哪个节点？
保留一个列表
view。按深度优先遍历，并记录深度，先遍历右子节点，再遍历左子节点；当节点的深度等于view的长度时，将该节点追加到列表中。也可以使用队列，每轮遍历一层：追加每轮的最后一个节点。
题解
你看到每一层最右侧的节点，它不一定是右子节点：示例 1 的最后一个值位于左子树中。广度优先搜索会让该节点成为每一轮的最后一个节点；优先向右遍历的深度优先搜索，则会在遇到该层的其他节点之前先遇到它。
广度优先，每一层的最后一个节点
思路
每轮处理树的一层。每轮开始时，队列中恰好按从左到右的顺序存放一层节点，因此本轮出队的最后一个节点就是该层最右侧的节点，并将它的值加入答案。
在示例 1 中，各轮依次为 [5]、[2, 9]、[7, 4, 1] 和 [3]，每轮的最后一个元素组成 5, 9, 1, 3。关键在于节点所在的层，而不是它位于哪一侧：3 位于左子树中，但它在这一层上是唯一的节点。
每个节点都只入队和出队一次，因此时间复杂度为 O(n)。队列最多扩展到最宽的一层，最坏情况下空间复杂度为 O(n)。
算法
- 将根节点的索引
0入队。 - 开始一轮处理时，保存队列的长度
s。 - 将
s个索引出队。对于每个索引i，如果2i+1和2i+2小于数组的长度且不等于-1，就依次将它们入队。 - 追加本轮最后一个出队索引对应的值。
- 重复上述步骤，直到队列为空，然后返回答案。
from collections import deque
def rightSideView(root):
n = len(root)
view = []
queue = deque([0]) # node indexes; the root is never empty
while queue:
size = len(queue) # exactly the nodes of the current level
for j in range(size):
i = queue.popleft()
if j == size - 1:
view.append(root[i]) # the last node of this level
for child in (2 * i + 1, 2 * i + 2):
if child < n and root[child] != -1:
queue.append(child)
return view深度优先，先访问右子节点
思路
按深度优先的顺序遍历，先尝试右子节点，再尝试左子节点，并记录深度，根节点的深度为 0。遍历第一次到达深度 d 时，答案中恰好有 d 个值。此时追加该节点的值，并忽略该层后续的所有节点。
第一个到达的节点就是最右侧的节点：无论两条通往某一层的路径在哪里分叉，遍历都会先沿右分支走到底，然后再回溯到左分支。在示例 1 中，遍历会访问 5, 9, 1, 2, 4, 7, 3：它会跳过 2、4 和 7，因为这些节点所在的深度已经有一个值，然后追加 3。
每个节点只访问一次，时间复杂度为 O(n)；栈上每层只有一次函数调用，最多 14 次。
算法
- 从空的答案开始，根节点的深度为 0。
- 跳过超出数组末尾的索引，或值为
-1的索引。 - 当答案的长度等于深度时，追加该值：遍历到达了新的一层，并且是从右侧到达的。
- 先递归遍历右子节点
2i+2，再递归遍历左子节点2i+1，每次深入一层。 - 返回答案。
def rightSideView(root):
n = len(root)
view = []
def visit(i, depth):
if i >= n or root[i] == -1:
return
if depth == len(view): # the first node met on this level
view.append(root[i])
# Right before left, so the rightmost node of every level comes first.
visit(2 * i + 2, depth + 1)
visit(2 * i + 1, depth + 1)
visit(0, 0)
return view
易错点和边界情况
- 只从根节点沿右子节点前进。例如，示例 1 会得到
[5, 9, 1]，并漏掉3；示例 2 会得到[6]。 - 读取每一层的最后一个位置，即
root[2^(d+1)-2]。在示例 2 中，索引 6 处是-1；可见的节点8位于索引 3。 - 跳过对子节点位置的长度检查。在示例 1 中，
3是最后一个条目，因此它的子节点位置 17 和 18 不存在。 - 先将右子节点加入队列，同时保留每一轮的最后一个节点。这样会收集到左视图，
[5, 2, 7, 3]。 - 在从右向左遍历时，让后面的节点覆盖前面的节点，这样也会得到左视图。
常见问题3
二叉树右视图的时间复杂度和空间复杂度是多少？
时间复杂度为 O(n)，其中 n 是节点数。任何解法都无法跳过节点，因为某一层最右侧的节点可能出现在任意位置。使用队列时，空间复杂度为 O(w)，其中 w 是最宽一层的宽度；在有 h 层的树上进行从右侧开始的遍历时，空间复杂度为 O(h)。
先左侧优先的深度优先搜索能解决它吗？
是的，如果你覆盖第一个值，而不是保留它。先从左侧开始遍历时，每一层的节点会从左到右依次遇到，因此要将每个节点的值存到它所在的深度，并让后面的节点替换前面的值。这样每一层最后留下的就是最右侧的值。时间复杂度仍为 O(n)，但每个节点都会写入一次。
这里应该使用广度优先搜索还是深度优先搜索？
两者都是线性的。广度优先搜索按照定义进行，每轮遍历一层。深度优先搜索只保留当前路径，因此在宽树上能节省内存，而且递归形式的代码还短几行。
def rightSideView(root):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
root = [5, 2, 9, 7, 4, -1, 1, -1, 3]
预期输出
[5, 9, 1, 3]