0652. 寻找重复的子树【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - DFS + 哈希表

1. 📝 题目描述

• leetcode

给你一棵二叉树的根节点 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

2. 🎯 s.1 - DFS + 哈希表

js

/**
 * @param {TreeNode} root
 * @return {TreeNode[]}
 */
var findDuplicateSubtrees = function (root) {
  const map = new Map()
  const res = []
  const dfs = (node) => {
    if (!node) return '#'
    const key = `${node.val},${dfs(node.left)},${dfs(node.right)}`
    const cnt = map.get(key) || 0
    if (cnt === 1) res.push(node)
    map.set(key, cnt + 1)
    return key
  }
  dfs(root)
  return res
}

py

class Solution:
    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:
        seen = defaultdict(int)
        res = []
        def dfs(node):
            if not node:
                return '#'
            key = f'{node.val},{dfs(node.left)},{dfs(node.right)}'
            if seen[key] == 1:
                res.append(node)
            seen[key] += 1
            return key
        dfs(root)
        return res

• 时间复杂度：$O(n^2)$，其中 n 是节点数，每个节点生成序列化字符串
• 空间复杂度：$O(n^2)$

算法思路：

• DFS 后序遍历，将每棵子树序列化为字符串
• 用哈希表记录每个序列化结果的出现次数，出现第 2 次时加入结果