LeetCode 652. 寻找重复的子树

约 6 分钟
文章信息 11 个分类 4 个标签
分类
LeetCode CodeTop 中等 未解决 5-10 字节 阿里 华为 微软 美团 携程
标签
哈希表 深度优先搜索 树 二叉树

题目描述

✅ 652. 寻找重复的子树

image-20260928235918291

image-20260928235918292

题意分析

以树中的每个节点为根，连同它的全部后代构成一棵子树。两棵子树只有在对应位置的节点值相同、左右结构也完全一致时才算重复，不能仅比较根节点值，也不能交换左右孩子。

对每一种出现至少两次的子树，只返回其中任意一个实际根节点。相同子树出现三次或更多次，答案中仍只保留一个代表，不需要复制整棵子树。

解法：后序遍历 + 子树 ID

核心思路

[!blue]

判断两棵树相同，本来就可以递归检查“根值相同、左子树相同、右子树相同”。把已经识别过的子树压缩成一个整数编号，就能用固定长度的三元组 (节点值, 左子树编号, 右子树编号) 表达这个条件，不必在每个祖先处重复保存完整的子树描述。

空节点固定返回编号 0，非空子树从 1 开始编号。必须先递归得到左右孩子的编号，再生成当前签名，因此使用后序遍历。signatureToId 保存签名与编号的对应关系：签名已存在就复用编号，第一次出现才分配新编号。

从空子树开始归纳，若左右孩子的编号能准确区分子树，那么相同三元组就意味着根值与左右子树都相同；三元组不同则至少有一处不同。因此当前节点的编号同样能准确区分整棵子树。这里编号是查表后分配的标识，不是直接拿哈希值作为结构编号。

frequency[id] 统计这种子树已经出现的次数。第一次只是登记，第二次才确认存在重复并加入当前根节点，第三次及以后不再加入。空节点直接返回 0，不参与计数或输出。

签名键也必须按内容比较。Java 用不可变的 List.of 保存三项，Go 用可以直接比较的 [3]int 数组；签名一旦入表便不再修改，左右编号的位置始终固定。

解题步骤

  1. 为本次调用创建编号表、频次数组和答案列表；频次的第 0 项留给空子树编号。
  2. 递归遇到空节点就返回 0，否则先取得左右子树编号。
  3. 用当前值和两个编号构造签名并查表。若是新签名，分配 表中已有签名数 + 1 作为编号，并补一个初始为零的频次位置。
  4. 将当前编号的频次加一，只有变为 2 时才收录当前节点。
  5. 把编号返回父节点，直到根节点处理结束，返回所有已收录的代表。

代码实现

class Solution {
    private Map<List<Integer>, Integer> signatureToId;
    private List<Integer> frequency;
    private List<TreeNode> answer;

    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        signatureToId = new HashMap<>();
        frequency = new ArrayList<>();
        // 编号零留给空节点
        frequency.add(0);
        answer = new ArrayList<>();
        getId(root);

        return answer;
    }

    private int getId(TreeNode node) {
        if (node == null) {
            return 0;
        }

        int leftId = getId(node.left);
        int rightId = getId(node.right);
        // 按值和有序左右编号识别结构，相同签名复用编号
        List<Integer> signature = List.of(node.val, leftId, rightId);
        Integer id = signatureToId.get(signature);

        if (id == null) {
            id = signatureToId.size() + 1;
            signatureToId.put(signature, id);
            frequency.add(0);
        }

        int seen = frequency.get(id) + 1;

        frequency.set(id, seen);

        // 只在第二次出现时报告，避免重复加入同一结构
        if (seen == 2) {
            answer.add(node);
        }

        return id;
    }
}

func findDuplicateSubtrees(root *TreeNode) []*TreeNode {
    signatureToID := make(map[[3]int]int)
    // 编号零留给空节点
    frequency := []int{
        0,
    }
    answer := make([]*TreeNode, 0)

    var getID func(*TreeNode) int
    getID = func(node *TreeNode) int {
        if node == nil {
            return 0
        }

        leftID := getID(node.Left)
        rightID := getID(node.Right)
        // 按值和有序左右编号识别结构，相同签名复用编号
        signature := [3]int{
            node.Val,
            leftID,
            rightID,
        }
        id, exists := signatureToID[signature]
        if !exists {
            id = len(signatureToID) + 1
            signatureToID[signature] = id
            frequency = append(frequency, 0)
        }

        frequency[id]++
        // 只在第二次出现时报告，避免重复加入同一结构
        if frequency[id] == 2 {
            answer = append(answer, node)
        }
        return id
    }

    getID(root)
    return answer
}

复杂度分析

  • 时间复杂度：期望 $O(n)$，其中 $n$ 为节点数。每个节点访问一次，三元组长度固定，哈希表查找与计数更新的期望开销均为 $O(1)$。
  • 空间复杂度：$O(n)$。不同子树类型至多有 $n$ 种，编号表和频次数组各占 $O(n)$；递归深度为树高 $h$，最坏也是 $O(n)$。答案只保存根节点引用，不复制子树。

关键点总结

[!green]

  • 编号代表完整子树，三元组的两项孩子编号把深层结构递归带入了当前签名。
  • 后序遍历保证孩子编号已经确定，空节点编号则保留了缺失孩子的位置。
  • “频次恰好变为二”同时完成重复确认与结果去重，不需要额外的已输出集合。

易错点总结

[!yellow]

  • 计数大于等于二就加入，会重复报告同一结构。
  • Java 使用普通数组作哈希键，会按对象身份而非三项内容比较。
  • 左右编号不区分，会把镜像结构当作相同子树。

相似题目

题目 难度 关联与区别
100. 相同的树 简单 完整相同树的条件来自节点值与两个孩子结构，本题把这个递归条件编码成签名后聚合。
609. 在系统中查找重复文件 中等 同样按内容签名查重，文件只比较字节内容，本题还必须编码子树结构。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2025/76202176
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！