Last updated on October 5th, 2024 at 03:57 pm

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

1. 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;
    }
};

2. 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;
    }
}

3. Find Duplicate Subtrees Leetcode 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
}

4. Find Duplicate Subtrees Leetcode 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