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.
1#include <unordered_map>
2#include <vector>
3#include <string>
4
5struct TreeNode {
6 int val;
7 TreeNode *left;
8 TreeNode *right;
9 TreeNode(int x) : val(x), left(NULL), right(NULL) {}
10};
11
12class Solution {
13public:
14 vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
15 unordered_map<string, vector<TreeNode*>> map;
16 serialize(root, map);
17 vector<TreeNode*> result;
18 for (auto& pair : map) {
19 if (pair.second.size() > 1) {
20 result.push_back(pair.second.front());
21 }
22 }
23 return result;
24 }
25
26private:
27 string serialize(TreeNode* node, unordered_map<string, vector<TreeNode*>>& map) {
28 if (!node) return "#";
29 string serial = to_string(node->val) + "," + serialize(node->left, map) + "," + serialize(node->right, map);
30 map[serial].push_back(node);
31 return serial;
32 }
33};This C++ solution uses a recursive DFS approach to serialize the tree, which is then stored in a hashmap. Duplicates are identified by checking hashmap entries with multiple nodes.
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.