Sponsored
Sponsored
Utilize a Depth-First Search (DFS) strategy and serialize each subtree. Treat the serialization as a key in a hashmap to track occurrences of identical subtrees. Duplicate entries are detected when a serialized key is encountered more than once.
Time Complexity: O(N), where N is the number of nodes since we visit each node once.
Space Complexity: O(N), accounting for the hashmap to store serialized trees and recursion stack space.
1class TreeNode:
2 def __init__(self, val=0, left=None, right=None):
3 self.val = val
4 self.left = left
5 self.right = right
6
7class Solution:
8 def findDuplicateSubtrees(self, root: TreeNode):
9 from collections import defaultdict
10 def serialize(node):
11 if not node:
12 return '#'
13 serial = f'{node.val},{serialize(node.left)},{serialize(node.right)}'
14 count[serial].append(node)
15 return serial
16
17 count = defaultdict(list)
18 serialize(root)
19 return [nodes[0] for nodes in count.values() if len(nodes) > 1]This Python solution uses DFS to serialize each subtree into a string. These strings are stored in a dictionary. If a string appears more than once, it indicates a duplicate subtree. The function returns one node from each set of duplicates.
Rather than using direct serialization strings, assign each unique subtree encountered a unique ID using a hash map. If a subtree's ID is seen again, it's a duplicate.
Time Complexity: O(N), as we traverse each node.
Space Complexity: O(N), necessary for dictionaries and recursive processing space.
1#include <unordered_map>
2#include <vector>
3
4struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
unordered_map<string, int> ids;
unordered_map<string, int> count;
vector<TreeNode*> result;
int idCounter = 1;
public:
vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
serialize(root);
return result;
}
private:
int serialize(TreeNode* node) {
if (!node) return 0;
string serial = to_string(node->val) + ',' + to_string(serialize(node->left)) + ',' + to_string(serialize(node->right));
if (!ids.count(serial)) {
ids[serial] = idCounter++;
}
int id = ids[serial];
if (++count[serial] == 2) {
result.push_back(node);
}
return id;
}
};This C++ implementation stands by using unique identifiers to serialize subtree structures uniquely. Duplicate subtrees' roots are identified through the repeated presence of the generated IDs.