Symmetric Tree
你会得到一个按层序存储在数组 tree 中的二叉树。根节点位于索引 0，索引 i 处节点的左子节点位于 2*i+1，右子节点位于 2*i+2，-1 表示空位置，数组末尾还可能有多余的 -1 项。如果这棵树沿着穿过根节点的垂直线呈镜像对称，则返回 true，否则返回 false。树的形状和值都必须匹配。
函数
- treeinteger-array
- 二叉树按层序排列，空位置用 -1 表示
- 返回值boolean
- 如果这棵树是镜像的，则为 true，否则为 false
约束条件
1 ≤ tree.length ≤ 32767- 每个
tree[i]都是-1，或者是满足0 ≤ tree[i] ≤ 1000的值。 tree[0]永远不会是-1，所以这棵树至少有一个节点。- 数组的末尾可能会在最后一个节点之后多出一些
-1条目。 - 空位置的两个子节点也都是空的，并且深度最多为
14。
示例
- 输入
- tree = [1, 2, 2, 3, 4, 4, 3]
- 输出
- true
- 解释
- 沿中间折叠这棵树。索引为
1和2的两个2会重合，索引为3和6的外侧两个3会重合，索引为4和5的内侧两个4会重合。
- 输入
- tree = [1, 2, 2, -1, 3, -1, 3]
- 输出
- false
- 解释
- 两个
3都挂在各自父节点的右侧。在镜像图中，左边2的右子节点（索引4）与右边2的左子节点（索引5）相对，而索引5为空。
- 输入
- tree = [4, 6, 6, 5, -1, -1, 9]
- 输出
- false
- 解释
- 这个形状是镜像：索引
3面向索引6，两者都包含一个节点。它们的值不同，一个是5，另一个是9，所以这棵树不对称。
进阶
如果这个形状是对称的，但有些值不同，那么至少需要更改多少个节点的值，才能让这棵树对称？
提示
逐个打开提示，每个都会多透露一点。
根节点的左子节点必须与哪个节点匹配？那个节点的左子节点又必须与哪个节点匹配？
每次比较两个位置。如果两个位置都为空，或者它们都存有相同的值，并且子节点交叉对应：一个位置的左子节点与另一个位置的右子节点互为镜像，一个位置的右子节点与另一个位置的左子节点互为镜像，那么它们就是镜像关系。
维护一个索引对栈，初始为
(1, 2)。弹出一对索引：如果两个位置都为空，就跳过；如果只有一个位置为空或两个值不同，就判定失败；否则压入(2*a+1, 2*b+2)和(2*a+2, 2*b+1)。
题解
每个节点在根节点另一侧的镜像位置都有一个对应节点，左子节点的对应节点是右子节点。让两边同时朝相反方向遍历，比较每对节点的结构和值，并在发现第一对不一致的节点时停止。
比较每个级别及其反向
思路
镜像图像从左到右和从右到左读起来都一样，因此每一层都必须把空位也写出来，并且从两个方向读起来都一样。在第二个示例中，底层读作 -1 3 -1 3，反过来则是 3 -1 3 -1，所以答案是 false。
空位必须保留在这一行中：如果不保留，这一层读起来就会是 3 3，从而通过检查。空位的子节点也为空，因此只有实际存在的节点才会添加条目。每个节点只访问一次，时间复杂度为 O(n)；内存中一次只保存一层，最宽层的宽度为 w 时，空间复杂度为 O(w)。
算法
- 从包含根索引
0的列表开始。 - 对于列表中的每个索引，按从左到右的顺序记录两个子节点的位置：如果子节点存在，就记录它的值；如果不存在，就记录
-1。收集存在的子节点，作为下一层的列表。 - 如果这一行与其反转后的内容不同，就返回
false。 - 在下一层重复这个过程，直到列表为空，然后返回
true。
def isSymmetric(tree):
n = len(tree)
level = [0] # the real nodes of one level, left to right
while level:
row = [] # the child spots under this level, -1 for an empty one
next_level = []
for i in level:
for child in (2 * i + 1, 2 * i + 2):
if child < n and tree[child] != -1:
row.append(tree[child])
next_level.append(child)
else:
row.append(-1)
if row != row[::-1]:
return False
level = next_level
return True对称对上的递归
思路
比较根节点的左子树（索引为 1）和右子树（索引为 2）。当两个位置都为空，或都包含相同的值且它们的子节点交叉对应时，这两个位置互为镜像：一个位置的左子节点与另一个位置的右子节点互为镜像（外侧的一对），一个位置的右子节点与另一个位置的左子节点互为镜像（内侧的一对）。这就是将镜像定义应用到下一层的结果，因此，如果每一对都匹配，整棵树就是镜像树。
每个实际节点最多属于一对，因此时间复杂度为 O(n)；调用栈的深度与树的高度相同，为 O(h)。
算法
- 编写
mirrors(a, b)。如果位置的索引超出末尾，或位置上的值为-1，则该位置为空。如果两个位置都为空，返回true；如果只有一个位置为空，返回false。 - 如果
tree[a]和tree[b]不同，返回false。 - 否则，返回
mirrors(2*a+1, 2*b+2)和mirrors(2*a+2, 2*b+1)。 - 返回
mirrors(1, 2)。没有子节点的根节点会对应两个空位置，因此结果为true。
def isSymmetric(tree):
n = len(tree)
def mirrors(a, b):
# Spots a and b must hold the same value, or both be empty.
empty_a = a >= n or tree[a] == -1
empty_b = b >= n or tree[b] == -1
if empty_a or empty_b:
return empty_a and empty_b
return (tree[a] == tree[b]
and mirrors(2 * a + 1, 2 * b + 2) # outer pair
and mirrors(2 * a + 2, 2 * b + 1)) # inner pair
return mirrors(1, 2)镜像对的显式栈
思路
递归只会记住仍待检查的节点对，所以你要自己用栈保存它们。检查顺序并不重要，因为只有每一对都匹配时，树才是对称的：栈按深度优先顺序检查，队列则按层次顺序检查。第三个示例在遇到第一个不匹配的节点对 (3, 6) 时就会停止，这对节点分别保存着 5 和 9。
每个实际节点最多只会出现在一对节点中，所以时间复杂度是 O(n)。栈中保存的待处理节点对数量大约等于当前路径的层数，空间复杂度是 O(h)。
算法
- 将配对
(1, 2)压入栈中。 - 弹出配对
(a, b)，并像mirrors那样测试它：如果两个位置都为空，就跳过；如果只有一个位置为空，或者两个值不同，则返回false。 - 否则，压入
(2*a+1, 2*b+2)和(2*a+2, 2*b+1)。 - 栈为空时，返回
true。
def isSymmetric(tree):
n = len(tree)
stack = [(1, 2)] # pairs of spots that must mirror each other
while stack:
a, b = stack.pop()
empty_a = a >= n or tree[a] == -1
empty_b = b >= n or tree[b] == -1
if empty_a and empty_b:
continue
if empty_a or empty_b or tree[a] != tree[b]:
return False
stack.append((2 * a + 1, 2 * b + 2)) # outer pair
stack.append((2 * a + 2, 2 * b + 1)) # inner pair
return True
易错点和边界情况
- 分别检查每棵子树。对于
[1, 2, 2, 3, 4, 4, 3]，左子树2, 3, 4并不对称，但整棵树是对称的：左子树必须是右子树的镜像。 - 错误地配对子节点。配对方式是
(2*a+1, 2*b+2)和(2*a+2, 2*b+1)，绝不能是(2*a+1, 2*b+1)。 - 只比较值。从
[1, 2, 2, -1, 3, -1, 3]中去掉空位后，每一层从两边读起来都相同，但这棵树并不对称。 - 读取超出末尾的位置。超出末尾的索引表示空位；只有一个节点的树根本没有索引
1或2。 - 在 Lua 和 R 中，数组从 1 开始：节点索引仍使用从 0 开始的编号，以便进行
2*i+1运算，并读取tree[i + 1]。
常见问题3
对称二叉树的时间复杂度是多少？
每个真实节点只会在一对镜像节点中比较一次，因此时间复杂度为 O(n)。递归版本和栈版本需要额外的 O(h) 空间，逐层处理的版本需要 O(w) 空间，其中 w 是最宽层的节点数。
对称树和两棵相同的树有什么区别？
比较左侧和左侧、右侧和右侧时，如果两棵树相同，它们就是相同的树。如果一棵树的左子树是右子树的镜像，那么这棵树就是对称的，因此比较时要交叉进行。两种情况都可以用同一组节点对检查，只需交换子节点的配对方式。
只有一个节点的树是对称的吗？
是的。它的两个空子节点位置互为镜像。只有一个子节点的根节点永远不对称，因为这个子节点面对的是一个空位置。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def isSymmetric(tree):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
tree = [1, 2, 2, 3, 4, 4, 3]
预期输出
true