Here, We see Find Duplicate Subtrees LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Find Duplicate Subtrees LeetCode Solution

Problem Statement

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]]

Find Duplicate Subtrees Leetcode Solution C++

class Solution {
public:
    vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
        unordered_map<string, int>m;
        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;
    }
};Code language: PHP (php)

Find Duplicate Subtrees Leetcode Solution Java

class Solution 
{
    HashMap<String, Integer> map= new HashMap<>();
    ArrayList<TreeNode> res= new ArrayList<>();
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) 
    {
        Mapper(root);
        return res;
    }
    public String Mapper(TreeNode root)
    {
        if(root == null)
            return "N";
        String left= Mapper(root.left);
        String right= Mapper(root.right);
        String curr= root.val +" "+left +" "+ right;
        map.put(curr, map.getOrDefault(curr, 0)+ 1);
        if(map.get(curr) == 2)
            res.add(root);
        return curr;
    }
}Code language: JavaScript (javascript)

Find Duplicate Subtrees Solution JavaScript

var findDuplicateSubtrees = function(root) {
  const map = new Map(), res = []
  dfs(root, map, res)
  return res
};
function dfs(root, map, res){
  if(!root) return '#'
  const subtree = `${root.val}.${dfs(root.left,map,res)}.${dfs(root.right, map,res)}`
  map.set(subtree,(map.get(subtree)||0) + 1)
  if(map.get(subtree) === 2){
    res.push(root)
  }
  return subtree
}Code language: JavaScript (javascript)

Find Duplicate Subtrees Solution Python

class Solution(object):
    def findDuplicateSubtrees(self, root):
        res = []
        hmap = {}
        def recurse(node, path):
            if node is None:
                return '#'
            path += ','.join([str(node.val), recurse(node.left, path), recurse(node.right, path)])
            if path in hmap:
                hmap[path] += 1
                if hmap[path] == 2:
                    res.append(node)
            else:
                hmap[path] = 1
            return path
        recurse(root, '')
        return res