652. Find Duplicate Subtrees
Problem 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.
Examples:
Example 1:
Input: root = [1,2,3,4,null,2,4,null,null,4] Output: [[2,4],[4]] Explanation: The duplicate subtrees are: - The subtree rooted at node with value 2 (shown in blue) - The subtree rooted at node with value 4 (shown in red)
Example 2:
Input: root = [2,1,1] Output: [[1]] Explanation: The duplicate subtree is the subtree rooted at node with value 1.
Example 3:
Input: root = [2,2,2,3,null,3,null] Output: [[2,3],[3]] Explanation: The duplicate subtrees are: - The subtree rooted at node with value 2 (shown in blue) - The subtree rooted at node with value 3 (shown in red)
Constraints:
- The number of nodes in the tree is in the range [1, 5000]
- -200 ≤ Node.val ≤ 200
Python Solution
class Solution:
def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:
def serialize(node, subtrees):
if not node:
return "#"
# Create a unique string representation of the subtree
serialized = f"{node.val},{serialize(node.left, subtrees)},{serialize(node.right, subtrees)}"
# Count occurrences of this subtree
if serialized in subtrees:
subtrees[serialized][1] += 1
else:
subtrees[serialized] = [node, 1]
return serialized
# Map to store serialized subtrees and their count
subtrees = {}
serialize(root, subtrees)
# Return roots of subtrees that appear more than once
return [node for node, count in subtrees.values() if count > 1]Alternative Solution (Using Tuple Serialization):
class Solution:
def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:
def tuplify(node, seen, duplicates):
if not node:
return None
# Create a tuple representation of the subtree
tup = (node.val,
tuplify(node.left, seen, duplicates),
tuplify(node.right, seen, duplicates))
# Check if we've seen this subtree before
if tup in seen:
if seen[tup] == 1: # First duplicate
duplicates.append(node)
seen[tup] += 1
else:
seen[tup] = 1
return tup
seen = {}
duplicates = []
tuplify(root, seen, duplicates)
return duplicatesImplementation Notes:
- First solution uses string serialization with O(n) space
- Second solution uses tuple serialization which can be more efficient
- Both solutions have O(n) time complexity where n is number of nodes
Java Solution
class Solution {
Map count;
List result;
public List findDuplicateSubtrees(TreeNode root) {
count = new HashMap<>();
result = new ArrayList<>();
serialize(root);
return result;
}
private String serialize(TreeNode node) {
if (node == null) {
return "#";
}
// Create a unique string representation of the subtree
String serialized = node.val + "," +
serialize(node.left) + "," +
serialize(node.right);
// Update count and add to result if it's a duplicate
count.put(serialized, count.getOrDefault(serialized, 0) + 1);
if (count.get(serialized) == 2) {
result.add(node);
}
return serialized;
}
} C++ Solution
class Solution {
unordered_map> subtrees;
string serialize(TreeNode* node) {
if (!node) {
return "#";
}
// Create a unique string representation of the subtree
string serialized = to_string(node->val) + "," +
serialize(node->left) + "," +
serialize(node->right);
// Update count and store node reference
if (subtrees.count(serialized)) {
subtrees[serialized].second++;
} else {
subtrees[serialized] = {node, 1};
}
return serialized;
}
public:
vector findDuplicateSubtrees(TreeNode* root) {
serialize(root);
vector result;
for (const auto& [_, pair] : subtrees) {
if (pair.second > 1) {
result.push_back(pair.first);
}
}
return result;
}
}; JavaScript Solution
/**
* @param {TreeNode} root
* @return {TreeNode[]}
*/
var findDuplicateSubtrees = function(root) {
const subtrees = new Map();
const result = [];
function serialize(node) {
if (!node) {
return '#';
}
// Create a unique string representation of the subtree
const serialized = `${node.val},${serialize(node.left)},${serialize(node.right)}`;
// Update count and add to result if it's a duplicate
const count = subtrees.get(serialized) || 0;
if (count === 1) {
result.push(node);
}
subtrees.set(serialized, count + 1);
return serialized;
}
serialize(root);
return result;
};C# Solution
public class Solution {
private Dictionary subtrees;
public IList FindDuplicateSubtrees(TreeNode root) {
subtrees = new Dictionary();
Serialize(root);
return subtrees.Values
.Where(x => x.Count > 1)
.Select(x => x.Node)
.ToList();
}
private string Serialize(TreeNode node) {
if (node == null) {
return "#";
}
// Create a unique string representation of the subtree
string serialized = $"{node.val},{Serialize(node.left)},{Serialize(node.right)}";
// Update count and store node reference
if (subtrees.ContainsKey(serialized)) {
var (existingNode, count) = subtrees[serialized];
subtrees[serialized] = (existingNode, count + 1);
} else {
subtrees[serialized] = (node, 1);
}
return serialized;
}
} Alternative Solution (Using Tuple Serialization):
public class Solution {
private Dictionary<(int Val, string Left, string Right), (TreeNode Node, int Count)> subtrees;
public IList FindDuplicateSubtrees(TreeNode root) {
subtrees = new Dictionary<(int, string, string), (TreeNode, int)>();
SerializeAsTuple(root);
return subtrees.Values
.Where(x => x.Count > 1)
.Select(x => x.Node)
.ToList();
}
private (int Val, string Left, string Right) SerializeAsTuple(TreeNode node) {
if (node == null) {
return (0, "#", "#");
}
var tuple = (node.val,
SerializeAsTuple(node.left).ToString(),
SerializeAsTuple(node.right).ToString());
if (subtrees.ContainsKey(tuple)) {
var (existingNode, count) = subtrees[tuple];
subtrees[tuple] = (existingNode, count + 1);
} else {
subtrees[tuple] = (node, 1);
}
return tuple;
}
} Implementation Notes:
- First solution uses string serialization for simplicity
- Second solution uses tuple serialization for better type safety
- Both solutions handle edge cases and maintain O(n) complexity