findDuplicateSubtrees.py

findDuplicateSubtrees.py

def findDuplicateSubtrees(self, root):
        def trv(root):
            if not root: return "null"
            struct = "%s,%s,%s" % (str(root.val), trv(root.left), trv(root.right))
            nodes[struct].append(root)
            return struct
        
        nodes = collections.defaultdict(list)
        trv(root)
        return [nodes[struct][0] for struct in nodes if len(nodes[struct]) > 1]

Constraints

Time Complexity: O(N), where N is the number of nodes in the tree. We visit each node once.

Space Complexity: O(N). Every structure we use is using O(1)O(1) storage per node.