友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
652. 寻找重复的子树
给你一棵二叉树的根节点 root ，返回所有 重复的子树。
对于同一类的重复子树，你只需要返回其中任意 一棵 的根结点即可。
如果两棵树具有 相同的结构 和 相同的结点值 ，则认为二者是 重复 的。
示例 1：
输入：root = [1,2,3,4,null,2,4,null,null,4] 输出：[[2,4],[4]]
示例 2：
输入：root = [2,1,1] 输出：[[1]]
示例 3：
输入：root = [2,2,2,3,null,3,null] 输出：[[2,3],[3]]
提示：
-
树中的结点数在
[1, 5000]范围内。 -
-200 <= Node.val <= 200
思路分析
深度优先遍历。先使用层级和数值对节点进行分流，相同高度和节点值的节点再尝试判断是否为相同子树。记录节点使用情况，添加过就不再处理。
-
一刷
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
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2026-04-20 22:08:01
*/
public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
Map<String, List<TreeNode>> numToNode = new HashMap<>();
Set<TreeNode> result = new HashSet<>();
// 先按层级进行分流
dfs(root, numToNode);
// 同一层级内的相互比较
for (List<TreeNode> value : numToNode.values()) {
if (value.size() == 1) {
continue;
}
// 添加过就直接跳过，不再参与计算
boolean[] used = new boolean[value.size()];
for (int i = 0; i < value.size(); i++) {
if (used[i]) {
continue;
}
for (int j = i + 1; j < value.size(); j++) {
if (used[j]) {
continue;
}
if (isSame(value.get(i), value.get(j))) {
used[i] = true;
used[j] = true;
result.add(value.get(i));
}
}
}
}
return new ArrayList<>(result);
}
private int dfs(TreeNode root, Map<String, List<TreeNode>> numToNode) {
if (Objects.isNull(root)) {
return 0;
}
int ll = dfs(root.left, numToNode);
int rl = dfs(root.right, numToNode);
int level = Math.max(ll, rl) + 1;
numToNode.computeIfAbsent(level + "/" + root.val, _ -> new ArrayList<>())
.add(root);
return level;
}
private boolean isSame(TreeNode root, TreeNode node) {
if (Objects.isNull(root) && Objects.isNull(node)) {
return true;
}
if ((Objects.nonNull(root) && Objects.nonNull(node) && root.val != node.val)
|| Objects.isNull(root)
|| Objects.isNull(node)) {
return false;
}
boolean left = isSame(root.left, node.left);
if (!left) {
return false;
}
return isSame(root.right, node.right);
}