> For the complete documentation index, see [llms.txt](https://jaywin.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jaywin.gitbook.io/leetcode/solutions/0652-find-duplicate-subtrees.md).

# 0652. Find Duplicate Subtrees

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

## Description

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)

```
**Input:** root = [1,2,3,4,null,2,4,null,null,4]
**Output:** [[2,4],[4]]
```

**Example 2:**

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

```
**Input:** root = [2,1,1]
**Output:** [[1]]
```

**Example 3:**

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

```
**Input:** root = [2,2,2,3,null,3,null]
**Output:** [[2,3],[3]]
```

**Constraints:**

* The number of the nodes in the tree will be in the range `[1, 10^4]`
* `-200 <= Node.val <= 200`

## ac1: serialize subtree

serialize subtree as a hash of the tree

<https://leetcode.com/problems/find-duplicate-subtrees/discuss/106011/Java-Concise-Postorder-Traversal-Solution>

```java
class Solution {
    List<TreeNode> duplicate;
    Map<String, Integer> map;

    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        duplicate = new ArrayList<>();
        map = new HashMap<>();

        process(root);

        return duplicate;
    }

    private String process(TreeNode node) {
        if (node == null) return "#";

        // String concatation is O(n), so overall is O(n^2)
        String hash = node.val + "," + process(node.left) + "," + process(node.right);

        map.put(hash, map.getOrDefault(hash, 0) + 1);

        if (map.get(hash) == 2) {
            // Only add one node for multiple duplicate subtrees.
            duplicate.add(node);
        }

        return hash;
    }
}
```