652. 寻找重复的子树
给定一棵二叉树，返回所有重复的子树。对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。
两棵树重复是指它们具有相同的结构以及相同的结点值。
链接
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| let treeMap = {}
let treeList: Array<TreeNode | null> = []
function findDuplicateSubtrees(root: TreeNode | null): Array<TreeNode | null> {
treeMap = {}
treeList = []
traverse(root)
return treeList
};
function traverse(root: TreeNode) : String {
if (root === null) {
return '#'
}
const left = traverse(root.left)
const right = traverse(root.right)
const res = left + ',' + right + ',' + root.val
if (!treeMap[res]) {
treeMap[res] = 'first'
} else if (treeMap[res] === 'first') {
treeMap[res] = 'no-first'
treeList.push(root)
}
return res
}
|
