Boundary Traversal of Binary Tree
数组 root 按层序存储一棵二叉树：根节点位于索引 0，索引 i 的子节点位于 2i+1（左）和 2i+2（右），空位置用 -1 表示，末尾还可能有多余的 -1。叶节点是没有子节点的节点。
按逆时针顺序返回边界：
- 根节点。
- 左边界，从上到下：从根节点的左子节点开始，如果有左子节点就向左走，否则向右走。遇到叶节点前停止。
- 所有叶节点，从左到右。
- 右边界，从下到上：与左边界镜像对称，从根节点的右子节点开始。
每个节点只列出一次，因此只有一个节点的树只返回根节点。
函数
- rootinteger-array
- 按层序遍历二叉树，空位置用 -1 表示
- 返回值integer-array
- 从根节点开始，逆时针方向排列的边界值
约束条件
1 ≤ root.length ≤ 32767- 每个
root[i]都是-1，或满足0 ≤ root[i] ≤ 105的值。 root[0]永远不会是-1，因此这棵树至少有一个节点。- 数组的最后一个节点之后可能还有多余的
-1项。 - 空位置的两个子节点也都是空的，且深度最多为
14。 - 节点值各不相同。
示例
- 输入
- root = [7, 3, 9, 1, 5, 8, -1, -1, -1, 4, 6]
- 输出
- [7, 3, 1, 4, 6, 8, 9]
- 解释
- 根节点
7之后，左边界是3：它的子节点1是叶节点。叶节点有1、4、6、8。右边界是9，位于叶节点8上方。
- 输入
- root = [10, 4, -1, -1, 6, -1, -1, -1, -1, 5, 8]
- 输出
- [10, 4, 6, 5, 8]
- 解释
4没有左子节点，因此左边界转向6，然后在叶节点5处停止。接下来是叶节点5、8。根节点没有右子节点。
- 输入
- root = [3]
- 输出
- [3]
- 解释
- 根节点是整棵树。它只列出一次，不会再次作为叶节点列出。
进阶
如何按顺时针顺序列出边界：根节点、从上到下的右边缘、从右到左的叶节点，然后是从下到上的左边缘？
提示
逐个打开提示，每个都会多透露一点。
把答案分成四部分：根节点、左边界、叶节点、右边界。哪些部分是沿着树向下的一条路径，哪些部分需要遍历整棵树？
每条边都是一条路径：从根节点的子节点开始，沿着同一侧继续走到子节点；如果这一侧为空，就走到另一侧的子节点。叶节点按从左到右的顺序排列，这个顺序来自先遍历左子树的深度优先遍历。注意连接处：边的终点所在的叶节点也属于叶节点集合。
从索引
1开始向下遍历，并追加每个非叶节点。然后用前序遍历追加每个叶节点。接着从索引2开始向下遍历，收集每个非叶节点，并按逆序追加该列表。
题解
答案由四部分组成：根节点、沿左边缘向下的路径、从左到右排列的叶节点，以及反向读取的沿右边缘向下的路径。在连接处，结束边缘的叶节点和作为叶节点的根节点都只能列出一次。
分别遍历这三个部分
思路
每条边对应一条路径：从根节点的子节点开始，依次列出节点，直到下一个节点将成为叶节点时停止，因为叶节点部分会列出它。前序遍历先走左侧再走右侧，因此会按从左到右的顺序遍历叶节点，因为无论深度如何，左子树中的所有节点都位于右子树的左侧。自顶向下收集右侧边界，再将其反转后追加。
每条边都沿一条路径遍历，叶节点遍历会访问每个节点一次：时间复杂度为 O(n)，递归深度为 h 层。
算法
- 从根节点开始；如果它是叶节点，就返回它。
- 从索引
1开始，当节点存在且不是叶节点时，将它添加进来，然后移动到它的左子节点；如果没有左子节点，则移动到右子节点。 - 从索引
1和2开始，按先序遍历，先访问左侧，并添加每个叶节点。 - 从索引
2开始，执行与步骤 2 相同的操作，但优先选择右子节点，并收集这些节点。 - 按相反顺序添加收集到的节点。
def boundaryTraversal(root):
n = len(root)
def real(i):
return i < n and root[i] != -1
def is_leaf(i):
return not real(2 * i + 1) and not real(2 * i + 2)
result = [root[0]]
if is_leaf(0):
return result
# 1. The left boundary, top-down, stopping before its leaf.
i = 1
while real(i) and not is_leaf(i):
result.append(root[i])
i = 2 * i + 1 if real(2 * i + 1) else 2 * i + 2
# 2. Every leaf: a pre-order walk meets them from left to right.
def add_leaves(i):
if not real(i):
return
if is_leaf(i):
result.append(root[i])
return
add_leaves(2 * i + 1)
add_leaves(2 * i + 2)
add_leaves(1)
add_leaves(2)
# 3. The right boundary, collected top-down and added bottom-up.
right = []
i = 2
while real(i) and not is_leaf(i):
right.append(root[i])
i = 2 * i + 2 if real(2 * i + 2) else 2 * i + 1
result.extend(reversed(right))
return result一次带边标记的前序遍历
思路
通过给每个节点标记一个标志，将这些遍历合并为一次基于栈的先序遍历：左边缘上的节点标记为 1，右边缘上的节点标记为 2，内部节点标记为 0。根节点的子节点分别从 1 和 2 开始。边缘节点会将自己的标志传给同一侧的子节点，或者传给唯一的子节点；其他子节点都标记为 0。在第二个示例中，1 从 4 传到 6，再传到 5。
节点从栈中取出时，将每个叶节点和每个标记为 1 的非叶节点追加到结果中；收集标记为 2 的非叶节点，并在最后将它们逆序追加。先序遍历会先到达所有左边缘节点，再到达任何叶节点，因为边缘只有在左侧没有节点时才会向右转。
算法
- 从根节点开始。将它的右子节点及标记
2入栈，然后将它的左子节点及标记1入栈。 - 弹出一个节点。如果它是叶节点或标记为
1，就将它追加到列表中；如果它不是叶节点且标记为2，就将它添加到右侧列表中。 - 将它的右子节点入栈，然后将左子节点入栈，并分别使用规则指定的标记。
- 栈为空时，将右侧列表反向后追加。
def boundaryTraversal(root):
n = len(root)
def real(i):
return i < n and root[i] != -1
result = [root[0]]
right = [] # the right boundary, top-down; it goes on the end reversed
# Each entry is (index, edge): 1 = left boundary, 2 = right boundary, 0 = inside.
stack = []
if real(2):
stack.append((2, 2))
if real(1):
stack.append((1, 1))
while stack:
i, edge = stack.pop()
has_left, has_right = real(2 * i + 1), real(2 * i + 2)
if not has_left and not has_right:
result.append(root[i]) # a leaf; pre-order meets them left to right
elif edge == 1:
result.append(root[i]) # the left boundary, top-down
elif edge == 2:
right.append(root[i])
# An edge passes to the child on its own side, or to an only child.
# The right child goes on the stack first, so the left one comes out first.
if has_right:
stack.append((2 * i + 2, edge if edge == 2 or not has_left else 0))
if has_left:
stack.append((2 * i + 1, edge if edge == 1 or not has_right else 0))
result.extend(reversed(right))
return result
易错点和边界情况
- 重复列出同一个节点。如果边界遍历没有在叶节点处停止，示例 1 中的
1就会被列出两次；只有一个节点的树不能再次将根节点列为叶节点。 - 把每一层的第一个节点当作左边界。如果根节点的左子节点是叶节点，而右子树更深，那么更深的层会从右子树的节点开始，但左边界为空。
- 只沿着左子节点遍历。在示例 2 中，边界必须从
4延伸到它的右子节点6。 - 逐层收集叶节点。这样，示例 1 会依次得到
1、8、4、6。 - 在 Lua 和 R 中，节点索引保持从 0 开始，以便进行
2i+1运算，并读取root[i + 1]。
常见问题3
什么是二叉树的边界遍历？
它按逆时针方向列出树的轮廓：根节点、从上到下的左边缘、从左到右的叶节点，以及从下到上的右边缘。边缘不包括叶节点，因此不会重复出现任何节点。
边界遍历的时间复杂度是多少？
O(n)。两次边界遍历各沿着一条路径进行，叶节点遍历会访问每个节点一次。递归或栈所需的额外空间为 O(h)。
左边界总是沿着左子节点延伸吗？
不是。有左子节点时，它会移到左子节点；否则会移到右子节点：也就是从左侧看到的最外层路径。如果根节点没有左子节点，左边界就是空的。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def boundaryTraversal(root):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
root = [7, 3, 9, 1, 5, 8, -1, -1, -1, 4, 6]
预期输出
[7, 3, 1, 4, 6, 8, 9]