Problem statement

https://leetcode.com/problems/find-duplicate-subtrees/

Solution 1

Note, that there will be exactly n different sub-trees. Let us do trees serialization for each tree and put all this to defaultdict. Classical serialization of tree is to visit node and children (does not matter in which order, but this order should be the same always: in the following code we use preorder traversal).

Complexity

Time and space complexity of this approach is O(n^2).

Code

class Solution(object):
    def findDuplicateSubtrees(self, root):
        def dfs(node):
            if not node: return "#"
            serial = str(node.val) + ":" + dfs(node.left) + ":" + dfs(node.right)
            trees[serial].append(node)
            return serial
        
        trees = defaultdict(list)
        dfs(root)
        return [trees[t][0] for t in trees if trees[t][1:]]

Solution 2

There is also O(n) time and space solution, using smarter way of hashing: let us for each node use key: its value and two values for left and right nodes: their unique hashes. If we did not found these key of 3 values, we add 1 to the biggest value in our defaultdict. So in this way in the end we will have unique identifiers for each subtree and also we add these identifiers to cands hash-table: so in the end we check it and return all nodes for which we have two or more trees.

Complexity

It is O(n) for time and space.

Code

class Solution(object):
    def findDuplicateSubtrees(self, root):
        def dfs(node):
            if not node: return
            key = (node.val, dfs(node.left), dfs(node.right))
            if key not in trees: trees[key] = len(trees)
            cands[trees[key]].append(node)
            return trees[key]
            
        trees = defaultdict()
        cands = defaultdict(list)
        dfs(root)
        return [cands[t][0] for t in cands if cands[t][1:]]

Remark

Note, that it is not the same as finding repeating patterns in strings, here we have only O(n) subtrees and in string we have O(n^2) substrings. See similar Problem 0572 Subtree of Another Tree, where we also used idea of tree serialization.