0652. 寻找重复的子树 #

标签：树、哈希表
难度：中等

题目大意 #

给定一个二叉树，返回所有重复的子树。对于重复的子树，只需返回其中任意一棵的根节点。

解题思路 #

对二叉树进行先序遍历，对遍历的所有的子树进行序列化处理，将序列化处理后的字符串作为哈希表的键，记录每棵子树出现的次数。

当出现第二次时，则说明该子树是重复的子树，将其加入答案数组。最后返回答案数组即可。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Solution:
    def findDuplicateSubtrees(self, root: TreeNode) -> List[TreeNode]:
        tree_dict = dict()
        res = []
        def preorder(node):
            if not node:
                return '#'
            sub_tree = str(node.val) + ',' + preorder(node.left) + ',' + preorder(node.right)
            if sub_tree in tree_dict:
                tree_dict[sub_tree] += 1
            else:
                tree_dict[sub_tree] = 1
            if tree_dict[sub_tree] == 2:
                res.append(node)
            return sub_tree
        preorder(root)
        return res