Left View of Binary Tree
你会得到一个按堆顺序存储在数组 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 = [3, 8, 5, -1, -1, -1, 6, -1, -1, -1, -1, -1, -1, 1]
- 输出
- [3, 8, 6, 1]
- 解释
8是一个叶节点，所以第三层和第四层只包含6（索引 6）和1（索引 13），它们都位于右子节点5下面。你仍然能看到它们：[3, 8, 6, 1]。
- 输入
- root = [10, -1, -1]
- 输出
- [10]
- 解释
- 索引 1 和 2 存放的是
-1，因此10没有子节点，视图中只有根节点。
- 输入
- root = [1, 2, 3, 4, 5, 6, 7]
- 输出
- [1, 2, 4]
- 解释
- 一棵完整的三层树。各层最左侧的位置索引分别是 0、1 和 3，其中存放着
1、2和4。
进阶
层级 d 填充索引 2^d-1 到 2^(d+1)-2。你能通过扫描这些范围来构建视图，而不使用队列或递归吗？在填充后的数组上，这样做的成本是多少？
提示
逐个打开提示，每个都会多透露一点。
你在某一层看到的节点不一定是左子节点。在示例 1 中，你在第三层看到的是哪个节点？它是谁的子节点？
按层对节点分组。如果你从左到右遍历每一层，你要找的节点就是这一层中遇到的第一个节点。
每轮按一层处理队列，并保留每轮的第一个节点。或者按深度优先遍历，记录深度，先遍历左侧再遍历右侧，并在节点深度等于目前记录的值的数量时记录该节点。
题解
如果左子树较短，从根节点开始沿着左子节点向下查找就会失败：在第一个示例中，下层节点是通过右子树看到的。你需要的是每一层的第一个节点。广度优先搜索会从左到右遍历每一层；优先向左的深度优先遍历会先遇到每一层最左侧的节点。
广度优先，每一层的第一个节点
思路
按轮次处理队列，就能一次得到一层。每轮开始时，队列中恰好有一个层级的节点，从左到右排列，因为本轮添加的每个子节点都会排在它后面。取出这么多个索引，按从左到右的顺序将每个节点的子节点加入队列，并保留第一个值。
在第一个示例中，各轮分别是 [3]、[8, 5]、[6] 和 [1]，保留的值依次为 3、8、6 和 1。8 不会添加任何内容，因为它的子节点位置 3 和 4 上都是 -1。
每个节点只进出队列一次：时间复杂度为 O(n)。队列会容纳整整一层的节点，在包含 14 层的满二叉树中，最多有 8192 个索引。
算法
- 创建一个队列，其中存放索引
0，并准备一个空答案。 - 当队列不为空时，令
s为队列的大小，并移除s个索引。追加第一个索引的值。 - 对于每个移除的索引
i，将2i+1、再将2i+2加入队列，跳过超出范围的索引以及值为-1的条目。
from collections import deque
def leftView(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 == 0:
view.append(root[i]) # the first 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深度优先，先遍历左子节点
思路
按深度优先遍历，先遍历左子树，再遍历右子树，并传递每个节点的深度。遍历在深度 d 首次到达的节点，就是第 d 层最左边的节点。取某一层最左边的节点 x 和它右侧的任意节点 y：在它们路径最后一个相交的节点处，x 向左走，y 向右走，而遍历会先完成左侧分支，再转向右侧。
遍历每次向下走一层，因此首次到达深度 d 时，答案中恰好有 d 个值。当 d 等于答案的长度时，记录该节点；不需要记录已访问深度的集合。
每个节点只访问一次，时间复杂度为 O(n)，内存中每层最多保存一次函数调用，这里最多为 14。R 版本会维护自己的栈，并先压入右子节点，再压入左子节点。
算法
- 创建一个空答案，并调用
visit(0, 0)。 - 在
visit(i, d)中，如果i超出数组范围，或root[i]为-1，则立即返回。 - 如果
d等于答案的长度，说明遍历首次到达第d层：追加root[i]。 - 调用
visit(2i+1, d+1)，然后调用visit(2i+2, d+1)。 - 第一次调用结束后，返回答案。
def leftView(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])
# Left before right, so the leftmost node of every level comes first.
visit(2 * i + 1, depth + 1)
visit(2 * i + 2, depth + 1)
visit(0, 0)
return view
易错点和边界情况
- 只从根节点沿左子节点向下查找。在第一个示例中，这样会停在
8，漏掉6和1。 - 读取每一层的第一个槽位，即
root[2^d-1]。在第一个示例中，第三层的第一个槽位（索引 3）存放的是-1，而这一层唯一的节点位于索引 6。 - 在深度优先遍历中先访问右子节点。这样，每一层最先遇到的节点就是最右侧的节点。
- 读取子节点时不检查边界。索引 13 处的
1的子节点位置是 27 和 28，超出了这个含 14 个元素的数组范围。
常见问题3
左侧视图是否与树的左边界相同？
不是。左边界是一条路径：它从根节点的左子节点开始，能向左就向左，否则向右，并在到达叶节点之前停止。左视图会从任意分支中每层取一个节点。在第一个示例中，左边界为空，因为 8 是叶节点，但左视图显示了 8、6 和 1。
左视图的时间复杂度和空间复杂度是多少？
两种答案都会查看每个节点一次，因此时间复杂度是 O(n)。广度优先搜索的队列会存放整层节点，对于一棵满二叉树来说，大约是节点总数的一半。优先遍历左侧的方式会为每一层保留一次函数调用，h 层时为 O(h)。
你要如何修改答案，才能得到正确的视图？
在广度优先版本中，保留每一轮的最后一个值，而不是第一个。在深度优先版本中，先访问右子节点，再访问左子节点；这样，遍历在每一层到达的第一个节点就是最右侧的节点。
def leftView(root):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
root = [3, 8, 5, -1, -1, -1, 6, -1, -1, -1, -1, -1, -1, 1]
预期输出
[3, 8, 6, 1]