-
Notifications
You must be signed in to change notification settings - Fork 0
/
652.寻找重复的子树.js
96 lines (92 loc) · 1.85 KB
/
652.寻找重复的子树.js
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
/*
* @lc app=leetcode.cn id=652 lang=javascript
*
* [652] 寻找重复的子树
*
* https://leetcode.cn/problems/find-duplicate-subtrees/description/
*
* algorithms
* Medium (58.32%)
* Likes: 436
* Dislikes: 0
* Total Accepted: 54.6K
* Total Submissions: 93.6K
* Testcase Example: '[1,2,3,4,null,2,4,null,null,4]'
*
* 给定一棵二叉树 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,10^4]范围内。
* -200 <= Node.val <= 200
*
*
*/
// @lc code=start
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {TreeNode[]}
*/
var findDuplicateSubtrees = function (root) {
// 记录重复的子树根节点
const ans = []
// 记录树出现的次数
const map = new Map()
const traverse = (root) => {
if (!root) return "#"
const left = traverse(root.left)
const right = traverse(root.right)
const str = `${left},${right},${root.val}`
// 获取已存入的树的次数
const count = map.get(str)
// 多次重复也只会被加入一次
if (count === 1) ans.push(root)
// 子树对应的出现次数加一
map.set(str, (count || 0) + 1)
return str
}
traverse(root)
return ans
}
// @lc code=end