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.
1class TreeNode:
2
This Python approach maps each subtree structure to a unique identifier, incrementally assigning IDs using a dictionary. Duplicates are recognized when the same ID appears multiple times.