blob: 5880fc82b1d59a1c7271d15bcf8099e96e54a6f9 (
plain)
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
|
// 652. Find Duplicate Subtrees
#include "leetcode.h"
/*
* given 'root' of a binary tree, return all duplicate subtrees. for each kind
* of duplicate, only return the root node of any one of them. two trees are
* duplicate if they have the same structure with the same node values.
*/
class Solution {
public:
vector<TreeNode *> findDuplicateSubtrees(TreeNode *root) {
unordered_map<string, vector<TreeNode *>> map;
vector<TreeNode *> dups;
serialise(root, map);
for (auto it = map.begin(); it != map.end(); it++)
if (it->second.size() > 1)
dups.push_back(it->second[0]);
return dups;
}
private:
string serialise(TreeNode *node,
unordered_map<string, vector<TreeNode *>> &map) {
string s = "(" + serialise(node->left, map) + to_string(node->val) +
serialise(node->right, map) + ")";
map[s].push_back(node);
return s;
}
};
|