-
Notifications
You must be signed in to change notification settings - Fork 0
/
0652-Find_Duplicate_Subtrees.cpp
162 lines (148 loc) · 4.28 KB
/
0652-Find_Duplicate_Subtrees.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
/*******************************************************************************
* 652-Find_Duplicate_Subtress.cpp
* Billy.Ljm
* 28 Feb 2023
*
* =======
* Problem
* =======
* https://leetcode.com/problems/find-duplicate-subtrees/description/
* Given the root of a binary tree, return all duplicate subtrees. For each kind
* of duplicate subtrees, you only need to return the root node of any one of
* them.Two trees are duplicate if they have the same structure with the same
* node values.
*
* ===========
* My Approach
* ===========
* My approach is hash the subtree (i.e. structure and node values) to be able
* to quickly compare across different locations in the parent tree. This is
* most efficiently done while recursively traversing the tree by hashing the
* leaves and then building up larger subtrees by hashing its combined left
* branch, right branch, and node.
*
* The time complexity of this will be O(n), where n is the number of nodes in
* the tree, assuming an O(1) hash like std::hash or std::unordered_map is used.
* The space complexity will also be identically O(n), since n hashes have to be
* constructed and stored.
******************************************************************************/
#include <iostream>
#include <vector>
#include <functional>
#include <unordered_map>
#include <string>
/**
* Definition for a binary tree node.
*/
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};
class Solution {
public:
/**
* Find all duplicate subtrees in a binary tree
*
* @param root root of binary tree to be checked
*
* @return vector of the roots of all duplicate subtrees
*/
std::vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
std::unordered_map<size_t, int> map; // hash-number of occurence
std::vector<TreeNode*> dupl; // duplicate subtrees
recurse(root, map, dupl); // recursively traverse tree
return dupl;
}
private:
/**
* Recursively traverse binary tree while hashing each subtree and counting
* each subtree's occurrence
*
* @param root root of subtree
* @param map hash table tracking number of occurrence of each subtree
* @param dupl vector of duplicate subtrees (one root node per duplicate)
*
* @return hash value of the subtree (at given root)
*/
size_t recurse(TreeNode* root, std::unordered_map<size_t, int>& map,
std::vector<TreeNode*>& dupl) {
// ignore ends of leaves
if (root == nullptr) {
return size_t(1);
}
// for branches, hash and check occurrence
else {
// hash; must distinguish left from right
size_t lefthash = recurse(root->left, map, dupl);
size_t righthash = recurse(root->right, map, dupl);
size_t hash = std::hash<std::string>{}(std::to_string(lefthash) +
std::to_string(righthash) + std::to_string(root->val));
// keep track of occurrences
if (map.count(hash) == 0) {
map[hash] = 1;
}
else {
map[hash]++;
};
// if second instance of duplicate, append to output
if (map[hash] == 2) {
dupl.push_back(root);
}
// return hash
return hash;
}
}
};
/**
* Print operator for trees (pre-order traversal)
*/
std::ostream& operator<<(std::ostream& os, const TreeNode* root) {
if (root == nullptr) {
os << "NULL";
}
else {
os << "[" << root->val << ",";
os << root->left << ",";
os << root->right << ",";
os << "\b]";
}
return os;
};
/**
* Print operator for the 1D vector class
*/
std::ostream& operator<<(std::ostream& os, const std::vector<int> vector) {
os << "[";
for (size_t i = 0; i < vector.size(); i++) {
os << vector[i] << ",";
}
os << "\b]";
return os;
};
std::ostream& operator<<(std::ostream& os, const std::vector<TreeNode*> vector) {
for (size_t i = 0; i < vector.size(); i++) {
os << vector[i] << ",";
}
return os;
};
/**
* Test Cases
*/
int main(void) {
Solution sol;
// test case 1
TreeNode* root1 = new TreeNode(1,
new TreeNode(2, new TreeNode(4), nullptr),
new TreeNode(3,
new TreeNode(2, new TreeNode(4), nullptr),
nullptr
)
);
std::vector<TreeNode*> dupl1 = sol.findDuplicateSubtrees(root1);
std::cout << "tree: " << root1 << "\ndupl: " << dupl1;
return 0;
}