寻找重复的子树

我将为您讲解一个关于哈希算法在树结构中的应用题目。这个题目要求找出二叉树中所有重复的子树。

题目描述

给定一棵二叉树，返回所有重复的子树。对于同一类的重复子树，您只需要返回其中任意一棵的根节点即可。

两棵树重复是指它们具有相同的结构以及相同的节点值。

示例：

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

重复子树：
  2    和    4
 /           \
4             4

解题思路分析

核心思路

我们需要识别出树中所有结构相同且节点值相同的子树。哈希表可以帮助我们记录每个子树的结构特征，从而快速判断是否重复。

关键步骤

1. 序列化子树：将每棵子树序列化为一个唯一的字符串表示
2. 哈希记录：使用哈希表记录每个序列化字符串出现的次数
3. 检测重复：当某个序列化字符串出现次数为2时，表示找到了重复子树

详细解题过程

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

为了在哈希表中比较子树是否相同，我们需要将子树转换为一个唯一的字符串标识。采用后序遍历的方式序列化子树：

def serialize(node):
    if node is None:
        return "#"  # 使用#表示空节点
    
    left_str = serialize(node.left)
    right_str = serialize(node.right)
    
    # 序列化格式：左子树 + 分隔符 + 右子树 + 分隔符 + 当前节点值
    return left_str + "," + right_str + "," + str(node.val)

步骤2：实现重复子树检测

使用哈希表记录每个序列化字符串的出现次数：

def findDuplicateSubtrees(root):
    from collections import defaultdict
    
    # 哈希表：序列化字符串 -> 出现次数
    subtree_count = defaultdict(int)
    # 结果列表
    result = []
    
    def traverse(node):
        if not node:
            return "#"
        
        # 序列化当前子树
        left_serialized = traverse(node.left)
        right_serialized = traverse(node.right)
        
        # 构建当前子树的序列化字符串
        serialized = left_serialized + "," + right_serialized + "," + str(node.val)
        
        # 更新哈希表
        subtree_count[serialized] += 1
        
        # 如果出现次数正好为2，说明找到了重复子树
        # 注意：只在次数为2时添加，避免重复添加相同的子树
        if subtree_count[serialized] == 2:
            result.append(node)
        
        return serialized
    
    traverse(root)
    return result

步骤3：优化序列化表示

为了减少字符串拼接的开销，我们可以使用更简洁的序列化方式：

def findDuplicateSubtrees_optimized(root):
    from collections import defaultdict
    
    subtree_count = defaultdict(int)
    result = []
    # 缓存序列化ID，避免重复计算
    serial_id_map = {}
    next_id = 1
    
    def traverse(node):
        nonlocal next_id
        
        if not node:
            return 0  # 使用0表示空节点
        
        # 递归序列化左右子树
        left_id = traverse(node.left)
        right_id = traverse(node.right)
        
        # 构建当前子树的唯一标识
        serial_key = (left_id, node.val, right_id)
        
        # 如果该序列化键已存在，直接返回对应的ID
        if serial_key in serial_id_map:
            serial_id = serial_id_map[serial_key]
        else:
            serial_id = next_id
            serial_id_map[serial_key] = serial_id
            next_id += 1
        
        # 更新出现次数
        subtree_count[serial_id] += 1
        if subtree_count[serial_id] == 2:
            result.append(node)
        
        return serial_id
    
    traverse(root)
    return result

算法复杂度分析

• 时间复杂度：O(N)，其中N是树中的节点数。每个节点只被访问一次。
• 空间复杂度：O(N)，用于存储哈希表和递归调用栈。

实际应用场景

这种基于哈希的子树匹配算法在以下场景中很有用：

1. 代码重复检测：在编译器中检测重复的语法树结构
2. 文档结构分析：比较XML或HTML文档的DOM树结构
3. 生物信息学：比较基因序列的树状结构
4. 代码克隆检测：在软件工程中识别重复的代码片段

关键要点总结

1. 序列化技巧：通过合适的序列化方法，可以将树结构转换为可哈希的键
2. 后序遍历：采用后序遍历可以自然地构建子树的序列化表示
3. 重复检测时机：只在计数为2时记录结果，避免重复记录相同的子树
4. 优化策略：使用ID映射可以减少字符串操作的开销，提高性能

这个算法展示了哈希表在树结构比较中的强大应用，通过巧妙的序列化方法，我们能够高效地解决子树匹配问题。