572 另一棵树的子树（树的哈希）

以你之姓@ 2022-08-31 11:06 166阅读 0赞

**1. 问题描述：**

给你两棵二叉树 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\]  
\-10 ^ 4 <= root.val <= 10 ^ 4  
\-10 ^ 4 <= subRoot.val <= 10 ^ 4  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/subtree-of-another-tree

**2. 思路分析：**

这是一道经典的**树的哈希**的题目，对于这道题目来说我们需要设计一个哈希函数使得两棵树的形态相同的时候哈希值是相同的，形态不同的时候哈希值大概率是不同的，常见的做法是将每一个对应的子树乘上质数然后将结果相加，也即t = (root.val + L \* P + R \* Q) % mod，L为左子树的哈希表，R为右子树的哈希值，P，Q分别是两个质数，为了防止结果太大造成溢出的情况我们可以考虑结果对mod取模，然后递归求解左右子树的哈希值，对于树的哈希，字符串哈希一般是不考虑冲突的情况。

**3. 代码如下：**

# class TreeNode:
    #     def __init__(self, val=0, left=None, right=None):
    #         self.val = val
    #         self.left = left
    #         self.right = right
    
    
    class Solution:
        P, Q, mod, T, res = 151, 157, 10 ** 9 + 7, -1, False
    
        def dfs(self, root: TreeNode):
            # 不能够返回0因为0可能是叶子节点例如[3,4,5,1,2,null,null,null,null,0] [4,1,2]结果应该是False, 可以随便返回不为0的数
            if not root: return 21
            left = self.dfs(root.left)
            right = self.dfs(root.right)
            x = (root.val % self.mod + self.mod) % self.mod
            if self.T == left or self.T == right: self.res = True
            # 返回当前节点构造的哈希表
            return (x + left * self.P + right * self.Q) % self.mod
    
        def isSubtree(self, s: TreeNode, t: TreeNode) -> bool:
            # 先递归的是子树然后修改
            self.T = self.dfs(t)
            # 因为两棵树可能完全是一样的所以需要判断一下根节点之前在递归的时候判断的都是左右子树
            if self.T == self.dfs(s): self.res = True
            return self.res