题目简介：
给定一棵二叉树 root，返回所有重复的子树。
对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。
如果两棵树具有相同的结构和相同的结点值，则它们是重复的。
示例 1：
1
2
| 输入：root = [1,2,3,4,null,2,4,null,null,4]
输出：[[2,4],[4]]
|
提示：
- 树中的结点数在
[1,10^4]范围内。
-200 <= Node.val <= 200
思路：
首先序列化子树，将其序列化为根节点值 + " " + 左子树序列化结果 + " " + 右子树序列化结果的形式，只要两个子树的序列化是相同的，则说明它们是重复的。所以通过map来存储序列化结果即可。
代码如下：
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
|
class Solution {
public:
unordered_map<string, int> map;
vector<TreeNode*> res;
string dfs(TreeNode* root){
if(!root)
return "";
string series = to_string(root -> val) + " " + dfs(root -> left) + " " + dfs(root -> right);
map[series]++;
if(map[series] == 2)
res.push_back(root);
return series;
}
vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
dfs(root);
return res;
}
};
|
