# 652. Find Duplicate Subtrees

Given the `root` of 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 the **same node values**.

**Example 1:**

![](https://assets.leetcode.com/uploads/2020/08/16/e1.jpg)

<pre><code><strong>Input: root = [1,2,3,4,null,2,4,null,null,4]
</strong><strong>Output: [[2,4],[4]]
</strong></code></pre>

***My Solutions:***

**方法1:**&#x20;

traverse树的时候用一个string储存树的结构，用一个map储存string出现的频率。如果频率出现两次，说明发现同样的subtree

```
class Solution {
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        List<TreeNode> res = new LinkedList<>();
        traverse(root, new HashMap<>(), res);
        return res;
    }
    
    public String traverse(TreeNode node, Map<String, Integer> cnt, List<TreeNode> res) {
        if (node == null) return "";
        String rep = "(" + traverse(node.left, cnt, res) + ")" + node.val + "(" + traverse(node.right, cnt, res) + ")";
        cnt.put(rep, cnt.getOrDefault(rep, 0) + 1);
        if (cnt.get(rep) == 2) res.add(node);
        return rep;
    }
}
```

**Complexity Analysis**

Let `n` denote the number of nodes.

Time: O(N \* N). The string representation of each subtree can have a length up to O(n). Creating each representation therefore costs up to O(n), and we find string representations for all O(n) subtrees during the traversal.

Space: O(N \* N). We store all string representations in the hash map. There are O(n) subtrees, and each subtree representation has the length of O(n).

**方法2:**&#x20;

Instead of representing a subtree with a string, we will use non-negative integer IDs: 0, 1, 2, and so on. Two subtrees are equal when they have equal root values, equal left subtrees, and equal right subtrees. Thus one can characterize a tree with the triplet (ID of the left subtree, root value, ID of the right subtree). Equal subtrees have the same triplets.

```
class Solution {
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        List<TreeNode> res = new LinkedList<>();
        traverse(root, new HashMap<>(), new HashMap<>(), res);
        return res;
    }

    public int traverse(TreeNode node, Map<String, Integer> tripletToID,
            Map<Integer, Integer> cnt, List<TreeNode> res) {
        if (node == null return 0;
        String triplet = traverse(node.left, tripletToID, cnt, res) + "," + node.val +
                "," + traverse(node.right, tripletToID, cnt, res);
        if (!tripletToID.containsKey(triplet)) {
            tripletToID.put(triplet, tripletToID.size() + 1);
        }
        int id = tripletToID.get(triplet);
        cnt.put(id, cnt.getOrDefault(id, 0) + 1);
        if (cnt.get(id) == 2) res.add(node);
        return id;
    }
}
```

因为tripletID的长度是O(1), 所以和方法1相比，方法2的复杂度都是O(N)

Time: O(N)

Space: O(N)