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.
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.