【2022-09-05每日一题】652. 寻找重复的子树
2022-09-05
2分钟阅读时长
2022-09-05每日一题：652. 寻找重复的子树
- 难度：Medium
- 标签：树 、 深度优先搜索 、 哈希表 、 二叉树
给定一棵二叉树 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
个人刷题记录，方便后续复习，具体解析思路请查看官方题解
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func findDuplicateSubtrees(root *TreeNode) []*TreeNode {
repeat := map[*TreeNode]struct{}{}
seen := map[string]*TreeNode{}
var dfs func (*TreeNode) string
dfs = func (node *TreeNode) string {
if node == nil {
return ""
}
// 序列化构造唯一key
serial := fmt.Sprintf("%d(%s)(%s)", node.Val, dfs(node.Left), dfs(node.Right))
if n, ok := seen[serial]; ok {
repeat[n] = struct{}{}
} else {
seen[serial] = node
}
return serial
}
dfs(root)
ans := make([]*TreeNode, 0, len(repeat))
for node := range repeat {
ans = append(ans, node)
}
return ans
}
复杂度分析
时间复杂度：O(n^2)
空间复杂度：O(n^2)
方法二：使用三元组进行唯一表示
个人刷题记录，方便后续复习，具体解析思路请查看官方题解
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func findDuplicateSubtrees(root *TreeNode) []*TreeNode {
type pair struct {
node *TreeNode
idx int
}
repeat := map[*TreeNode]struct{}{}
seen := map[[3]int]pair{}
idx := 0
var dfs func (*TreeNode) int
dfs = func (node *TreeNode) int {
if node == nil {
return 0
}
// 序列化构造唯一key
serial := [3]int{node.Val, dfs(node.Left), dfs(node.Right)}
if p, ok := seen[serial]; ok {
repeat[p.node] = struct{}{}
return p.idx
}
idx++
seen[serial] = pair{node, idx}
return idx
}
dfs(root)
ans := make([]*TreeNode, 0, len(repeat))
for node := range repeat {
ans = append(ans, node)
}
return ans
}
复杂度分析
- 时间复杂度：O(n)，其中 n 是树中节点的数目。
- 空间复杂度：O(n)，即为哈希表需要使用的空间。