难度: Easy
给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。
二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
示例 1：
输入：root = [3,4,5,1,2], subRoot = [4,1,2] 输出：true
示例 2：
输入：root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2] 输出：false
提示：
root 树上的节点数量范围是 [1, 2000]subRoot 树上的节点数量范围是 [1, 1000]-104 <= root.val <= 104-104 <= subRoot.val <= 104运行时间: 42 ms
内存: 16.3 MB
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
def searchsub(root):
if not root:
return 0
return ((root.val + 1000079) + (searchsub(root.left) * 31 + searchsub(root.right) * 179)) % int(1e10 + 7)
num = searchsub(subRoot)
ans = [False]
def searchmain(root):
if not root:
return 0
val = ((root.val + 1000079) + (searchmain(root.left) * 31 + searchmain(root.right) * 179)) % int(1e10 + 7)
if val == num:
ans[0] = True
return val
searchmain(root)
return ans[0]
该题解使用了哈希的思想。首先通过 searchsub 函数计算出子树 subRoot 的哈希值，然后在主树 root 中通过 searchmain 函数查找是否存在一个子树的哈希值与 subRoot 的哈希值相等。如果存在，则说明主树中包含了与 subRoot 结构相同的子树，返回 True；否则返回 False。在计算哈希值时，使用了节点的值、左子树的哈希值和右子树的哈希值，并通过质数相乘的方式组合，以尽量避免哈希冲突。
时间复杂度: O(m + n)
空间复杂度: O(n)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
def searchsub(root):
if not root:
return 0
# 计算子树的哈希值
return ((root.val + 1000079) + (searchsub(root.left) * 31 + searchsub(root.right) * 179)) % int(1e10 + 7)
# 计算子树 subRoot 的哈希值
num = searchsub(subRoot)
ans = [False]
def searchmain(root):
if not root:
return 0
# 计算主树的哈希值
val = ((root.val + 1000079) + (searchmain(root.left) * 31 + searchmain(root.right) * 179)) % int(1e10 + 7)
# 比较主树的哈希值与子树的哈希值
if val == num:
ans[0] = True
return val
searchmain(root)
return ans[0]
哈希方法被选择来解决这个问题主要是因为它在某些情况下可以提供比简单递归方法更高的效率。使用哈希方法，我们可以将每个节点的子树转化为一个哈希值，这样就可以通过比较哈希值来快速判断两个子树是否相同，而不需要再进行逐节点的比较。这种方法尤其在树的结构复杂或树的大小较大时，可以显著减少比较次数和运行时间。然而，这种方法可能需要额外的空间来存储每个节点的哈希值，并且还需要处理哈希冲突的问题。
在哈希函数中使用特定的质数，如31、179和1000079，是为了减少哈希冲突的概率并尽可能均匀地分布哈希值。质数在哈希函数中常用来这种目的，因为它们在进行模运算时不易产生规律性，从而帮助更随机地分布哈希值。选用不同的质数组合可以根据具体的应用场景调整，以达到最佳的哈希效果。1000079这样的大质数通常用于最终的模运算，以限制哈希值的范围并减少冲突。
在题解中，哈希冲突的处理似乎没有被直接提及。理想情况下，如果哈希值相同，我们应该进一步检查两棵树的结构和节点值以确保它们确实相同，因为不同的树可能会有相同的哈希值（尽管这种情况较少）。在实际应用中，当我们发现两个哈希值相同时，可以再通过递归的方式对这两棵子树进行详细比较，确保它们在结构和节点值上完全一致。这一步骤是必要的，以避免因哈希冲突而错误地判断两棵树相同。