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 <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4#include <unordered_map>
5#include <vector>
6
7struct TreeNode {
8 int val;
9 struct TreeNode *left;
10 struct TreeNode *right;
11};
12
13char* serialize(struct TreeNode* node, std::unordered_map<std::string, std::vector<struct TreeNode*>>& map) {
14 if (!node) return "#";
15 char* left = serialize(node->left, map);
16 char* right = serialize(node->right, map);
17 std::string serial = std::to_string(node->val) + "," + std::string(left) + "," + std::string(right);
18 map[serial].push_back(node);
19 return strdup(serial.c_str());
20}
21
22std::vector<struct TreeNode*> findDuplicateSubtrees(struct TreeNode* root) {
23 std::unordered_map<std::string, std::vector<struct TreeNode*>> map;
24 serialize(root, map);
25 std::vector<struct TreeNode*> result;
26 for (auto& pair : map) {
27 if (pair.second.size() > 1) {
28 result.push_back(pair.second.front());
29 }
30 }
31 return result;
32}This C solution serializes the tree into strings using recursive DFS. A hashmap is employed to track these serialized strings and identify duplicates. Nodes with duplicate serials 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.