652 寻找重复的子树（树的哈希）

朱雀 2022-08-29 09:39 75阅读 0赞

**1. 问题描述：**

给定一棵二叉树，返回所有重复的子树。对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。两棵树重复是指它们具有相同的结构以及相同的结点值。

**示例 1：**  
1  
/ \\  
2 3  
/ / \\  
4 2 4  
/  
4  
下面是两个重复的子树：  
2  
/  
4  
和  
4  
因此，你需要以列表的形式返回上述重复子树的根结点。  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/find-duplicate-subtrees

**2. 思路分析：**

首先最简单的方法是将每一棵子树映射为字符串存储到哈希表中，这样当某一棵子树之前出现过那么在哈希表中的值是存在的，但是使用哈希表来存储整棵树的字符串哈希值的时候，在查找和存储整棵树节点的时间复杂度和空间复杂度都是非常高的，如果使用类似于字符串哈希的方法将某一棵子树通过哈希函数映射为一个整数提交上去有些答案是错误的，也即存在冲突的，所以这两种方法都不是特别正确。这里我们采用的方法是将当前根节点以及左右子树映射为一个三元组对应的字符串形式存储到哈希表ids中，当前子树对应的三元组的值使用一个递增的count变量来维护（这样每一棵子树是可以被唯一标识的），当我们发现之前的不存在当前子树的时候说明需要更新count变量了，表示新的子树，否则当前子树还是哈希表中三元组映射的字符串的整数值，这样就可以将树中的每一棵子树映射为三元组对应的整数值，也即子树==> 整数的映射，并且我们是在递归的过程中来维护这个映射的，所以只有当子树==>整数的映射是一一对应的两棵子树才是相等的，所以子树与三元组是一一映射的关系。并且我们另外一个哈希表来记录相同子树出现的次数，这样才可以判断子树出现的次数是否大于等于2，所以我们需要声明一个哈希表dic来记录三元组映射为整数出现的次数，也即相同子树出现的次数，当发现子树出现的次数大于等于2的时候就将当前的根节点加入到答案中。

**3. 代码如下：**

from typing import List
    import collections
    
    
    class TreeNode:
        def __init__(self, val=0, left=None, right=None):
            self.val = val
            self.left = left
            self.right = right
    
    
    class Solution:
        # ids用来子树与三元组的一一映射, dic记录子树出现的次数, count递增来唯一标识一棵子树, res记录答案对应的根节点
        ids, dic, res, count = None, None, None, 0
    
        def dfs(self, root: TreeNode):
            if not root: return 0
            left = self.dfs(root.left)
            right = self.dfs(root.right)
            key = str(left) + " " + str(right) + str(root.val)
            # 出现了新的子树说明需要更新count, count变量可以唯一标识每一棵子树, 子树相同的时候count值是相同的
            if key not in self.ids:
                self.count += 1
                self.ids[key] = self.count
            # 当当前的子树之前是存在过的那么哈希表存储的还是原来的值, 否则更新为当前的count值
            i = self.ids[key]
            self.dic[i] += 1
            # 为了避免重复加入某一棵子树所以这样当出现次数为2的时候才添加对应的子树的根节点
            if self.dic[i] == 2:
                self.res.append(root)
            # i可以唯一标识每一棵子树
            return i
    
        # 类似于树的哈希
        def findDuplicateSubtrees(self, root: TreeNode) -> List[TreeNode]:
            self.ids = dict()
            self.dic = collections.defaultdict(int)
            self.res = list()
            self.count = 0
            self.dfs(root)
            return self.res