哈希算法题目：寻找重复的子树

题目描述
给定一棵二叉树的根节点 root，返回所有重复的子树。对于同一类的重复子树，只需返回其中任意一棵的根节点即可。如果两棵树具有相同的结构和节点值，则认为它们是重复的。

示例
输入：root = [1,2,3,4,null,2,4,null,null,4]
输出：[[2,4],[4]]
解释：

• 子树 [4] 出现多次（叶子节点 4 和子树中的 4）。
• 子树 [2,4] 也重复出现（以节点 2 为根的子树）。

解题思路

1. 问题分析：需要比较所有子树的结构和值，快速判断是否重复。直接递归比较每棵子树的时间复杂度会很高（O(n^2)）。
2. 关键思路：将每棵子树序列化为唯一的字符串（如后序遍历），用哈希表记录每个序列出现的次数。当某个序列出现次数为 2 时，说明发现重复子树。
3. 优化点：
   • 序列化时避免字符串拼接开销，可用三元组 (根值,左子树ID,右子树ID) 代替完整字符串。
   • 通过给每个唯一子树分配唯一 ID（如自增编号），减少存储和比较成本。

详细步骤

步骤 1：设计子树序列化方法

• 采用后序遍历（左→右→根）序列化子树，确保结构唯一性。
• 示例：子树 [2,4] 序列化为 "4,2,null"（假设空节点用 "null" 表示）。
• 但直接拼接字符串在子树较大时效率低，需优化。

步骤 2：优化序列化——唯一标识符（ID）映射

• 维护一个全局字典 seen，键为子树序列化字符串，值为该子树出现的次数。
• 同时维护一个字典 id_map，将序列化字符串映射到唯一 ID（整数），用 ID 代替字符串比较。
• 序列化时，递归返回当前子树的 ID，而非完整字符串。

步骤 3：递归遍历与重复判断

1. 定义全局变量：
   • id_counter：用于分配唯一 ID 的自增计数器。
   • seen：记录每个子树 ID 的出现次数。
   • result：存储重复子树的根节点列表。
2. 递归函数 traverse(node)：
   • 如果节点为空，返回特殊 ID（如 0 代表空节点）。
   • 递归获取左子树 ID left_id 和右子树 ID right_id。
   • 生成当前子树的三元组标识符 (node.val, left_id, right_id)。
   • 若该标识符首次出现，为其分配新 ID 并加入 id_map，计数初始化为 1。
   • 若已存在，则从 id_map 获取其 ID，并将计数加 1。
   • 当计数恰好为 2 时，将当前节点加入 result（避免重复添加）。
3. 返回当前子树的 ID。

步骤 4：示例推导
以示例 root = [1,2,3,4,null,2,4,null,null,4] 为例：

• 叶子节点 4 的三元组为 (4,0,0)（左右子节点为空）。
• 子树 [2,4] 的三元组为 (2, (4,0,0)的ID, 0)。
• 当第二次遇到相同的三元组时，计数变为 2，记录根节点。

代码实现（Python）

def findDuplicateSubtrees(root):
    from collections import defaultdict
    id_map = {}  # 三元组 -> ID
    id_counter = 1  # ID 从 1 开始，0 保留给空节点
    seen = defaultdict(int)  # ID -> 出现次数
    result = []

    def traverse(node):
        if not node:
            return 0  # 空节点 ID 为 0
        
        left_id = traverse(node.left)
        right_id = traverse(node.right)
        
        # 当前子树的三元组标识符
        triplet = (node.val, left_id, right_id)
        
        if triplet not in id_map:
            nonlocal id_counter
            id_map[triplet] = id_counter
            id_counter += 1
        
        subtree_id = id_map[triplet]
        seen[subtree_id] += 1
        if seen[subtree_id] == 2:
            result.append(node)
        
        return subtree_id

    traverse(root)
    return result

复杂度分析

• 时间复杂度：O(n)，每个节点仅处理一次，三元组哈希操作为 O(1)。
• 空间复杂度：O(n)，存储所有子树的 ID 映射和计数。