# 652 Find Duplicate Subtrees

## 652. Find Duplicate Subtrees

## 1. Question

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.

## 2. Implementation

(1) Post order traversal + HashMap

```java
 public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        List<TreeNode> res = new ArrayList<>();
        Map<String, Integer> map = new HashMap<>();

        postOrderTraversal(root, map, res);

        return res;
    }

    public String postOrderTraversal(TreeNode node, Map<String, Integer> map, List<TreeNode> res) {
        if (node == null) {
            return "#";
        }

        String leftCode = postOrderTraversal(node.left, map, res);
        String rightCode = postOrderTraversal(node.right, map, res);

        String curCode = node.val + leftCode + rightCode;

        if (map.getOrDefault(curCode, 0) == 1) {
            res.add(node);
        }
        map.put(curCode, map.getOrDefault(curCode, 0) + 1);
        return curCode;
    }
```

## 3. Time & Space Complexity

Post order traversal + HashMap: 时间复杂度: O(n), 空间复杂度: O(n)