Algorithm
Problem Name: 652. Find Duplicate Subtrees
Problem Link: https://leetcode.com/problems/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;
}
};
Input
root = [1,2,3,4,null,2,4,null,null,4]
Output
[[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) {
ans.add(node);
}
}
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;
}
}
Input
root = [1,2,3,4,null,2,4,null,null,4]
Output
[[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
}
Input
root = [2,1,1]
Output
[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]
Input
root = [2,1,1]
Output
[1]]