Find Duplicate Subtrees

Intuition

We could first serialize each subtree recursivly and then judge if the serialization of each subtree occurs more than once by string.count method.

Solution


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
from collections import defaultdict


class Solution:
    def findDuplicateSubtrees(self, root: TreeNode) -> List[TreeNode]:
        self.str = self._serialize(root)
        self.ans = defaultdict(list)
        self._find_duplicate(root)
        return [v[0] for v in self.ans.values()]

    def _serialize(self, node):
        if node is None:
            return ''
        return '[%d](%s)(%s)' % (node.val,
                self._serialize(node.left),
                self._serialize(node.right))

    def _find_duplicate(self, node):
        if node is None:
            return ''
        s = '[%d](%s)(%s)' % (node.val,
                self._find_duplicate(node.left),
                self._find_duplicate(node.right))
        if self.str.count(s) > 1:
            self.ans[s].append(node)
        return s