LeetCode每日一题——652. 寻找重复的子树

题目

给定一棵二叉树 root，返回所有重复的子树。

对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。

如果两棵树具有相同的结构和相同的结点值，则它们是重复的。

示例

示例 1：

输入：root = [1,2,3,4,null,2,4,null,null,4]
输出：[[2,4],[4]]

示例 2：

输入：root = [2,1,1]
输出：[[1]]

示例 3：

输入：root = [2,2,2,3,null,3,null]
输出：[[2,3],[3]]

提示：

树中的结点数在[1,10^4]范围内。
-200 <= Node.val <= 200

思路

先想的是如何存放这个树，但是半天没想出来，借鉴了官方的做法，使用dfs将树的每个节点的子树序列化为 根节点(左子树)（右子树）的字符串形式并存在哈希表中，若发现哈希表中有该序列，则为重复的子树。

题解

class Solution:
    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:
        def dfs(node: Optional[TreeNode]) -> str:
        	# 空树返回空字符串
            if not node:
                return ""
            #  序列化特定形式
            serial = "".join([str(node.val), "(", dfs(node.left), ")(", dfs(node.right), ")"])
            #	判重
            if seen.get(serial):
                tree = seen.get(serial)
                repeat.add(tree)
            else:
                seen[serial] = node
            
            return serial
        
        seen = dict()
        repeat = set()

        dfs(root)
        return list(repeat)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23