652. Find Duplicate Subtrees

from collections import defaultdict
class Solution(object):
    def findDuplicateSubtrees(self, root):
        """
        :type root: TreeNode
        :rtype: List[TreeNode]
        """
        def tupify(root):
            if root:
                sub = root.val, tupify(root.left), tupify(root.right)
                subtrees[sub].append(root)
                return sub
        subtrees = defaultdict(list)
        tupify(root)
        res = []
        for i in subtrees.values():
            if len(i) > 1:
                res.append(i[0])
        return res
        # return [node[0] for i in subtrees.values() if node[1:]]

'''
1.save the subtree structure as a tuple 2.build a dictionary to make the structure as a key and node as value

it takes O(n) time complexity and O(n) space '''

HanchengZhao / algorithm-notes

652. Find Duplicate Subtrees #13