0%

leetcode652寻找重复的子树

题目地址

https://leetcode-cn.com/problems/find-duplicate-subtrees/

题目描述

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
给定一棵二叉树,返回所有重复的子树。对于同一类的重复子树,你只需要返回其中任意一棵的根结点即可。

两棵树重复是指它们具有相同的结构以及相同的结点值。

示例 1:

1
/ \
2 3
/ / \
4 2 4
/
4

下面是两个重复的子树:

2
/
4



4

因此,你需要以列表的形式返回上述重复子树的根结点。

代码实现

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
javascript
var findDuplicateSubtrees = function(root) {

// 初始化一个map用来记录字符串出现次数
const map = new Map();
// 初始化用来存储结点的数组
const res = [];

function findDuplicateSubtrees1(root) {
// 后序遍历二叉树得到以每一个结点为根的树的序列化结果,空结点用'#'表示
if (!root) {
return '#';
}
const left = findDuplicateSubtrees1(root.left);
const right = findDuplicateSubtrees1(root.right);
const str = left + ',' + right + ',' + root.val;

// 如果字符串出现超过一次,就往数组中添加其对应的结点
if (map.has(str)) {
if (map.get(str) === 1) {
res.push(root);
}
map.set(str, map.get(str)+1);
}else {
map.set(str, 1);
}

return str;
}
findDuplicateSubtrees1(root);
return res;
};