LeetCode: 652. Find Duplicate Subtrees

All we have to do is traversing every node by dfs and checking whether current node's structure is already seen or not.

Then, we need to come up with a way to 'represent' a tree's structure. Here, we use a string to represent the tree structure. --> str(node.val) + (left tree structure) + (right tree structure)

If it is a new string, we add to our dictionary (self.dp).

If it is a already seen string, we check if it is seen for the second time with its value (self.dp[string]).

Time complexity: O(N)

Space Complexity: 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 findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:
        self.dp = {}
        self.ret = []
        self.dfs(root)
        return self.ret
        
    def dfs(self, node):
        if not node:
            return ""
        left, right = self.dfs(node.left), self.dfs(node.right)
        ret = str(node.val) + '(' + left + ')' + '(' + right + ')'
        if ret not in self.dp:
            self.dp[ret] = True
        else:
            if self.dp[ret]:
                self.ret.append(node)
                self.dp[ret] = False
        return ret