## Algorithm

Problem Name: 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:

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

Example 2:

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

Example 3:

```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, 5000]`
• `-200 <= Node.val <= 200`

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
unordered_mapm;
vector < TreeNode*>res;
DFS(root, m, res);
return res;
}

string DFS(TreeNode* root, unordered_map < string, int>& m, vector<TreeNode*>& res){
if(!root) return "";
string s = to_string(root->val) + "," + DFS(root->left, m, res) + "," + DFS(root->right, m, res);
if(m[s]++ == 1) res.push_back(root);
return s;
}
};
``````
Copy The Code &

Input

cmd
root = [1,2,3,4,null,2,4,null,null,4]

Output

cmd
[[2,4],[4]]

### #2 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
Map map;

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

helper(root);

for (TreeNode node : map.values()) {
if (node != null) {
}
}

return ans;
}

private String helper(TreeNode root) {
if (root == null) {
return "#";
}

String path = root.val + "|" + helper(root.left) + "|" + helper(root.right);
map.put(path, map.containsKey(path) ? root : null);

return path;
}
}
``````
Copy The Code &

Input

cmd
root = [1,2,3,4,null,2,4,null,null,4]

Output

cmd
[[2,4],[4]]

### #3 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const findDuplicateSubtrees = function(root) {
const hash = {}, res = []
pre(root, hash, res)
return res
};

function pre(node, hash, res) {
if(node == null) return '#'
const str = `\${node.val},\${pre(node.left, hash, res)},\${pre(node.right, hash, res)}`
if(hash[str] == null) hash[str] = 0
hash[str]++
if(hash[str] === 2) res.push(node)
return str
}
``````
Copy The Code &

Input

cmd
root = [2,1,1]

Output

cmd
[1]]

### #4 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def findDuplicateSubtrees(self, root):
def dfs(root):
if not root: return "null"
struct = "%s,%s,%s" % (str(root.val), dfs(root.left), dfs(root.right))
nodes[struct].append(root)
return struct

nodes = collections.defaultdict(list)
dfs(root)
return [nodes[struct][0] for struct in nodes if len(nodes[struct]) > 1]
``````
Copy The Code &

Input

cmd
root = [2,1,1]

Output

cmd
[1]]