# 652 Find Duplicate Subtrees

Given a binary tree, return all duplicate subtrees. For each kind of duplicate subtrees, you only need to return the root node of any **one** of them.

Two trees are duplicate if they have the same structure with same node values.

**Example 1:**

```
        1
       / \
      2   3
     /   / \
    4   2   4
       /
      4
```

The following are two duplicate subtrees:

```
      2
     /
    4
```

and

```
    4
```

Therefore, you need to return above trees' root in the form of a list.

**The Idea:** Copy all the sub-trees in the tree. In order to obtain a unique kind of identification, run a preorder traversal that accumulates the root values, as well `None`. In order to obtain a unique identification for every sub-tree, a dictionary of lists will map each unique sub-tree identifier with it's associated root. It would then follow that duplicate sub-trees will have 2 or more roots associated with a key.

**Complexity:** O(n) time and O(n^2) space

```python
def findDuplicateSubtrees(self, root):
    """
    :type root: TreeNode
    :rtype: List[TreeNode]
    """
    serials = collections.defaultdict(list)

    def copyAllSubtrees(root):
        if root is not None:
            subtree = "%s,%s,%s" % (root.val, copyAllSubtrees(root.left), copyAllSubtrees(root.right))
            serials[subtree].append(root)
            return subtree
        else:
            return "#"

    copyAllSubtrees(root)
    return [roots[0] for serial, roots in serials.items() if len(roots) > 1]
```