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.
1function TreeNode(val) {
2 this.val = val;
3 this.left = this.right = null;
4}
5
6var findDuplicateSubtrees = function(root) {
7 const map = new Map();
8 function serialize(node) {
9 if (!node) return '#';
10 const serial = `${node.val},${serialize(node.left)},${serialize(node.right)}`;
11 if (!map.has(serial)) {
12 map.set(serial, []);
13 }
14 map.get(serial).push(node);
15 return serial;
16 }
17 serialize(root);
18 const result = [];
19 for (const nodes of map.values()) {
20 if (nodes.length > 1) {
21 result.push(nodes[0]);
22 }
23 }
24 return result;
25};This JavaScript solution serializes subtrees into strings via DFS, storing those strings in a map. Duplicate strings imply duplicate subtrees, and such occurrences are returned.
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.
1function TreeNode(val)
This JavaScript approach assigns unique identifiers for each different subtree structure encountered. Duplicate IDs signal subtrees that share the same structure and value arrangements.