Subtree of Another Tree
给你两棵二叉树，root 和 subRoot，它们都按层序存储在数组中：根节点位于索引 0，索引 i 的子节点分别位于 2*i+1（左侧）和 2*i+2（右侧），空位置用 -1 表示。数组末尾可能有多余的 -1 项。
如果 root 中存在某个节点，且该节点及其所有后代的形状和值都与 subRoot 完全相同，则返回 true；否则返回 false。整个 root 也算在内。
函数
- rootinteger-array
- 要搜索的树，按层序排列，空位置用 -1 表示
- subRootinteger-array
- 要查找的树，格式保持一致
- 返回值boolean
- 如果 subRoot 作为一个节点出现在 root 中，且其所有后代节点也都包含在内，则为 true，否则为 false
约束条件
1 ≤ root.length ≤ 32767且1 ≤ subRoot.length ≤ 32767- 每个条目都是
-1，或介于0到104之间的值。 root[0]和subRoot[0]都不为-1，因此两棵树至少各有一个节点。- 任一数组的末尾都可能在最后一个节点之后多出一些
-1项。 - 空位置的两个子节点也都是空的，并且每棵树的深度最多为
14。 - 值可以重复。
示例
- 输入
- root = [6, 2, 8, 1, 3, -1, 9]subRoot = [2, 1, 3]
- 输出
- true
- 解释
- 索引
1处的节点2的子节点是1和3，它们都是叶节点。这正是subRoot。
- 输入
- root = [6, 2, 8, 1, 3, -1, 9, -1, -1, 0]subRoot = [2, 1, 3]
- 输出
- false
- 解释
- 节点
2下方的3现在有一个子节点0。子树包含所有后代节点，因此节点2包含四个节点，而subRoot有三个，并且没有其他节点包含2。
- 输入
- root = [5, 5, 7]subRoot = [5]
- 输出
- true
- 解释
- 根节点
5有两个子节点，因此它与单个节点5不匹配。索引1处的5是叶节点，符合条件。
进阶
你能根据每棵子树的值及其子节点的指纹，为每棵子树生成指纹，从而让它与 subRoot 的比较只需 O(1) 时间吗？如果两棵不同的子树发生哈希冲突，你该怎么办？
提示
逐个打开提示，每个都会多透露一点。
如果
subRoot出现在root中，它的顶部会位于root的某个节点上。这个节点可能是哪些节点？你要在这些节点上检查什么？编写一个函数，用来判断两棵树是否相同：两棵树都为空，或者顶部的值相同，且左子树和右子树分别相同。一个位置为空而另一个位置有实际节点，说明它们不同。
从
root的每个节点运行这项检查。要跳过大多数节点，请先计算每个节点的高度：只有高度等于subRoot高度的节点才可能匹配。
题解
这个问题分为两部分：判断两棵树是否相同，以及选择在 root 中的哪个位置运行检查。只有高度等于 subRoot 高度的节点才可能匹配，而且同一高度的节点不会重叠，因此只检查这些节点，就能确保 root 中的每个节点最多被遍历一次。
在每个节点进行比较
思路
当 i 位于数组范围内，且该位置的值不是 -1 时，这个位置才是有效位置。当两棵树都为空，或者它们的根节点值相同，并且左子树和右子树分别相同时，这两棵树才相同。same(i, j) 从 i 开始遍历 root，同时从 j 开始遍历 subRoot。如果 subRoot 出现在 root 中，它的根节点就位于某个节点上，因此要从每个有效的 i 开始尝试 same(i, 0)。
对于每个 n 个节点中的节点，近似匹配最多可以进行 m 步才失败：O(n·m)。这里，深度上限限制了遍历次数：一个节点只会被从它自身或它上方节点开始的检查遍历，最多 14 次。
算法
- 编写
same(i, j)。如果root中位置i和subRoot中位置j都为空，则返回true；如果只有一个为空，则返回false。 - 如果两个值不同，则返回
false。否则，返回same(2*i+1, 2*j+1)和same(2*i+2, 2*j+2)。 - 如果
root中存在有效索引i，使得same(i, 0)成立，则返回true；否则返回false。
def isSubtree(root, subRoot):
n, m = len(root), len(subRoot)
def same(i, j):
# True if the subtree at root[i] equals the subtree at subRoot[j].
a = i < n and root[i] != -1
b = j < m and subRoot[j] != -1
if not a or not b:
return a == b # two empty spots match, one empty spot does not
if root[i] != subRoot[j]:
return False
return same(2 * i + 1, 2 * j + 1) and same(2 * i + 2, 2 * j + 2)
# Try every real node of root as the top of a match.
for i in range(n):
if root[i] != -1 and same(i, 0):
return True
return False仅在高度相同时进行比较
思路
相同的树具有相同的高度，高度按向下最长路径上的节点数计算。因此，只有 root 中高度等于 subRoot 高度的节点才值得检查。在第一个示例中，subRoot 的高度是 2，而 root 中只有 2 和 8 符合条件。
一个节点总是比它下面的所有节点都高，因此两个高度相同的节点不会一个包含在另一个里面。每次检查只遍历起始节点的子树，所以所有检查加起来，root 中的每个节点最多只会被遍历一次。
子节点的索引比父节点大，因此从最后一个索引开始向前扫描时，会先遍历两个子节点，再遍历父节点。两次高度扫描和这些检查总共需要 O(n + m) 时间。
算法
- 从最后一个索引向下扫描，为每棵树填充高度数组：空位置的高度为
0，真实节点的高度为1加上两个子节点中较大的高度。 - 对于
root中高度等于subRoot在索引0处的高度的每个索引i，运行same(i, 0)，如果结果为真，就返回true。 - 返回
false。
def isSubtree(root, subRoot):
n, m = len(root), len(subRoot)
def same(i, j):
# True if the subtree at root[i] equals the subtree at subRoot[j].
a = i < n and root[i] != -1
b = j < m and subRoot[j] != -1
if not a or not b:
return a == b # two empty spots match, one empty spot does not
if root[i] != subRoot[j]:
return False
return same(2 * i + 1, 2 * j + 1) and same(2 * i + 2, 2 * j + 2)
def heights(tree):
# Children sit at larger indexes, so a backward scan finishes them first.
h = [0] * len(tree)
for i in range(len(tree) - 1, -1, -1):
if tree[i] != -1:
left = h[2 * i + 1] if 2 * i + 1 < len(tree) else 0
right = h[2 * i + 2] if 2 * i + 2 < len(tree) else 0
h[i] = 1 + max(left, right)
return h
target = heights(subRoot)[0]
rootHeights = heights(root)
# Only a node of the same height can match, and no two such nodes overlap.
for i in range(n):
if rootHeights[i] == target and same(i, 0):
return True
return False
易错点和边界情况
- 接受部分匹配，例如第二个示例。
root中的某个节点有值，而subRoot对应位置为空时，same必须返回失败。 - 在遇到第一个值正确的节点时就停止。在第三个示例中，根节点
5不匹配，而它下方的叶节点5匹配。 - 比较两个数组的切片。子树的节点分布在多个层级中，而且任一数组末尾都可能有额外的
-1项。超出数组末尾的索引表示空位，就像-1一样。 - 在 Lua 和 R 中，节点索引保持从 0 开始，以便进行
2*i+1运算，并读取root[i + 1]。
常见问题3
另一棵树的子树的时间复杂度是多少？
从每个节点开始比较，在最坏情况下的时间复杂度为 O(n·m)，其中 n 和 m 是两棵树的大小。只在高度等于 subRoot 高度的节点处进行比较，可将时间复杂度降至 O(n + m)，因为这样每个 root 节点最多只会遍历一次。
可以用字符串匹配解决另一个树的子树问题吗？
是的。按前序遍历写出每棵树，为每个空子节点写上 #，并在每个值前加上分隔符：,2,1,#,#,3,#,#。只有当 subRoot 的字符串出现在 root 的字符串中时，它才是子树；KMP 可以在 O(n + m) 时间内找到它。如果不加标记，不同形状的树会得到相同的字符串；如果不加分隔符，12 就会包含 2。
一个与 subRoot 匹配但有额外子节点的节点也算吗？
不。子树是一个节点及其所有后代，因此匹配节点下的每个节点也必须出现在 subRoot 中。在第二个示例中，3 下多出的 0 使答案变为 false。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def isSubtree(root, subRoot):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
root = [6, 2, 8, 1, 3, -1, 9] subRoot = [2, 1, 3]
预期输出
true