Invert Binary Tree
你会得到一个按层序存储在数组 tree 中的二叉树。根节点位于索引 0 处，索引 i 处节点的左子节点和右子节点分别位于 2*i+1 和 2*i+2 处，-1 表示空位置，并且数组末尾可能有多余的 -1 项。
反转这棵树：交换每个节点的左子节点和右子节点，使整棵树变成镜像。以相同形式返回反转后的树，末尾不能有 -1 项。
函数
- treeinteger-array
- 按层序遍历二叉树，空位置用 -1 表示
- 返回值integer-array
- 按层序遍历镜像树，不包含末尾的 -1 项
约束条件
1 ≤ tree.length ≤ 16383- 每个
tree[i]都是-1，或是满足0 ≤ tree[i] ≤ 1000的值。 tree[0]永远不会是-1，因此这棵树至少有一个节点。- 数组可能会在最后一个节点后面多出一些
-1项。 - 空位置的两个子节点也都是空的，并且深度最多为
14。
示例
- 输入
- tree = [5, 3, 8, 1, 4, -1, 9]
- 输出
- [5, 8, 3, 9, -1, 4, 1]
- 解释
- 根节点的子节点
3和8交换位置。它们下面，原先在3下方的1和4现在变成了4和1；而原先只有右子节点9的8，现在这个子节点位于它的左侧。
- 输入
- tree = [2, 7, -1, 6]
- 输出
- [2, -1, 7, -1, -1, -1, 6]
- 解释
2、7、6组成的链向左倾斜，因此它的镜像向右倾斜：7从索引1移到2，6从3移到6。答案比输入更长。
- 输入
- tree = [1, -1, -1]
- 输出
- [1]
- 解释
- 单个节点就是它自己的镜像。两个
-1条目是填充，答案会删除末尾的所有-1。
进阶
如何在不构建翻转副本的情况下，使用相同的索引对检查一棵树是否与自身互为镜像？
提示
逐个打开提示，每个都会多透露一点。
根节点仍位于索引
0。它的左子节点在镜像树中会位于哪里？想一想，一个节点的位置与其父节点的位置有什么关系。如果索引为
src的节点落在索引dst处，它的左子节点会落在2*dst+2处，右子节点会落在2*dst+1处。每个节点都保持在自己的层级上，因此向上取整到整层的输出总有足够空间。用
-1填充输出，然后从(0, 0)开始，用成对元素组成的队列进行遍历。对于每一对，将值复制到另一侧，并把真实子节点及其交换后的位置加入队列。最后删除末尾的-1项。
题解
镜像会交换每个节点的左子树和右子树。这里，节点的位置由它的索引表示，因此交换两棵子树会移动其中的所有节点。改为在一个新数组中构建答案，并在遍历过程中传递一对索引：节点当前的位置，以及它镜像后要去的位置。
递归将每个节点放置在其镜像索引处
思路
根节点始终位于索引 0。一个节点的左子树会变成其镜像节点的右子树，因此，如果索引 src 处的节点被放到 dst，它的左子节点会被放到 2*dst+2，右子节点会被放到 2*dst+1。这样就得到了 place(src, dst)，它会复制一个值，并用交换后的目标位置递归处理两个子节点。在第一个示例中，索引 1 处的 3 会被放到 2，所以它的子节点 1 和 4 会被放到 6 和 5。
节点所在的层级不会改变，但它的镜像索引可能超出输入的末尾。将输出大小设为包含完整层级（1, 3, 7, 15, ...）：在第二个示例中，长度 4 会变成 7，从而为索引 6 处的 6 留出空间。每个节点只放置一次，因此时间复杂度为 O(n)，输出占用 O(n) 空间，调用栈最多有 14 个栈帧。
算法
- 将长度向上取整为
size = 2^k - 1，并用-1填充该长度的输出。 - 编写
place(src, dst)：如果src超出末尾，或者tree[src]为-1，则返回。 - 否则，设置
out[dst] = tree[src]，然后调用place(2*src+1, 2*dst+2)和place(2*src+2, 2*dst+1)。 - 调用
place(0, 0)，删除末尾的-1项，然后返回输出。
def invertTree(tree):
n = len(tree)
size = 1
while size < n: # round up to whole levels, so every mirrored index fits
size = 2 * size + 1
out = [-1] * size
def place(src, dst):
if src >= n or tree[src] == -1:
return
out[dst] = tree[src]
place(2 * src + 1, 2 * dst + 2) # the left subtree goes to the right
place(2 * src + 2, 2 * dst + 1) # the right subtree goes to the left
place(0, 0)
last = size - 1
while out[last] == -1: # trim the trailing -1 entries
last -= 1
return out[:last + 1]使用索引对队列进行广度优先搜索
思路
同样的配对方法也适用于队列。从 (0, 0) 开始；每次取出一个配对，就复制一个值，并将每个真实子节点及其交换后的目标位置加入队列。交换操作会写入目标索引，因为数组无法在一步之内交换两个子树。每个真实节点都会进入队列一次，并带上它应该所在的位置。
时间复杂度为 O(n)，队列最多保存 O(w) 个配对，其中 w 是最宽层的宽度。不会出现调用栈溢出。
算法
- 将长度向上取整到完整的层数，并用
-1填充同样大小的输出。 - 将数对
(0, 0)放入队列。 - 从队首取出数对
(src, dst)，并设置out[dst] = tree[src]。 - 对于数组内且不为
-1的每个子节点，将(2*src+1, 2*dst+2)和(2*src+2, 2*dst+1)放入队列。 - 队列为空时，删除末尾的
-1项，并返回输出。
def invertTree(tree):
n = len(tree)
size = 1
while size < n: # round up to whole levels, so every mirrored index fits
size = 2 * size + 1
out = [-1] * size
queue = [(0, 0)] # pairs: index in tree, index of its mirrored spot in out
head = 0
while head < len(queue):
src, dst = queue[head]
head += 1
out[dst] = tree[src]
left, right = 2 * src + 1, 2 * src + 2
if left < n and tree[left] != -1:
queue.append((left, 2 * dst + 2)) # the left child goes to the right
if right < n and tree[right] != -1:
queue.append((right, 2 * dst + 1)) # the right child goes to the left
last = size - 1
while out[last] == -1: # trim the trailing -1 entries
last -= 1
return out[:last + 1]
易错点和边界情况
- 直接交换
tree[2*i+1]和tree[2*i+2]。这样交换的是两个值，而不是它们的子树：在第一个示例中，1和4仍然位于8下面。 - 让输出和输入一样长。第二个示例中的
6会落在输入的最后一个索引之后。 - 忘记删掉末尾的
-1项，无论是填充过的输入，还是比输入更早结束的镜像都要处理。 - 在 Lua 和 R 中，别忘了数组从 1 开始。对于
2*i+1的运算，请保留从 0 开始的索引，并读取tree[i + 1]。
常见问题3
反转二叉树是什么意思？
反转二叉树会将它变成镜像：每个节点的左子树和右子树都会交换位置。根节点保持不变，左侧链会变成右侧链。反转两次，树就会恢复原样。
反转二叉树的时间复杂度是多少？
每个节点都会访问一次，所以时间复杂度是 O(n)。对于深度为 h 的树，递归会使用 O(h) 的栈空间，队列会使用 O(w) 的空间，其中 w 是最宽层的节点数。在这个数组版本中，答案是一个新数组，因此会额外占用 O(n) 的空间。
为什么翻转二叉树会反转每一层？
镜像会在所有位置翻转左右，因此每一层的节点都会以相反的顺序出现。按层遍历时，每一层的切片都会反转：切片 [1, 4, -1, 9] 会变成 [9, -1, 4, 1]。将最后一层用 -1 补齐后，再反转每一层，也是适用于这种布局的第三种 O(n) 答案。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def invertTree(tree):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
tree = [5, 3, 8, 1, 4, -1, 9]
预期输出
[5, 8, 3, 9, -1, 4, 1]