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

字数 1571 2025-12-10 11:47:16

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

题目描述
给定一棵二叉树，你需要找出所有重复的子树。对于同一类的重复子树，你只需要返回其中任意一棵的根节点即可。两棵二叉树重复是指它们具有相同的结构以及相同的节点值。

示例
输入：

输出：返回两棵重复子树的根节点列表，顺序不限。上例中重复的子树是：

   2
  / 
 4

和单个节点 4。

解题过程循序渐进讲解

第一步：理解问题与目标
我们需要找出二叉树中所有结构完全相同的子树，并且每种结构只返回一个代表根节点。
难点在于：如何高效地判断两棵子树是否相同？如果对每对子树都进行递归比较，时间复杂度会很高。
优化思路：将每棵子树“序列化”成一个唯一的字符串（或其他可哈希的标识），用哈希表存储已出现过的子树结构，从而快速判断重复。

第二步：设计子树标识（哈希键）
一种常用的方法是：用后序遍历的方式，将子树序列化成字符串。
例如，对于一棵子树，我们可以生成一个像 "4,2,1" 这样的字符串（假设我们用后序遍历，并用逗号分隔节点值，空节点可以用特殊符号如 "#" 表示）。
具体规则：

空节点表示为 "#"。
非空节点生成字符串格式：左子树字符串,右子树字符串,当前节点值。
这样，相同结构的子树一定会生成相同的字符串，不同结构的子树几乎不会碰撞（除非刻意构造，但通常可以忽略）。

第三步：遍历树并构建哈希表
我们使用深度优先搜索（后序遍历）访问每个节点：

如果节点为空，返回 "#"。
递归得到左子树的序列化字符串，再递归得到右子树的序列化字符串。
将当前子树序列化为：左字符串 + "," + 右字符串 + "," + 节点值。
在哈希表（HashMap<String, Integer>）中记录这个字符串出现的次数。
如果某个字符串出现次数刚好为 2（表示第二次遇到），就将当前节点加入结果列表（避免重复添加多次）。

第四步：示例推导
以上面的示例树为例，我们模拟后序遍历过程：

节点 4（左下方的叶子）：左空、右空，序列化："#,#,4"。哈希表记录："#,#,4" 出现 1 次。
节点 2（左下方的那个）：左子树是 "#,#,4"，右空，序列化："#,#,4,#,2"。记录出现 1 次。
节点 4（中间的叶子）："#,#,4"，这是第二次出现 "#,#,4"，次数变为 2，所以将节点 4 加入结果。
节点 2（右子树中的那个）：左子树 "#,#,4"，右空，序列化："#,#,4,#,2"，这是第二次出现这个字符串，所以将节点 2 加入结果。
继续遍历其他节点，但没有新的重复了。
最终结果包含两个节点：值为 4 的叶子节点（代表单节点子树），和值为 2 的节点（代表结构 (4) 的子树）。

第五步：实现细节
我们可以用一个 List<TreeNode> 存放结果，用 Map<String, Integer> 记录每个序列化字符串的出现次数。
递归函数返回当前子树的序列化字符串。
注意：因为字符串拼接可能比较耗时，也可以考虑用唯一ID（如给每个不同的序列分配一个数字ID）来优化，但字符串方法更直观。

第六步：伪代码

findDuplicateSubtrees(root):
    初始化结果列表 result
    初始化哈希表 map (字符串 -> 出现次数)
    递归函数 serialize(node):
        如果 node 为空: 返回 "#"
        左字符串 = serialize(node.left)
        右字符串 = serialize(node.right)
        当前子树序列 = 左字符串 + "," + 右字符串 + "," + node.val
        如果 map[当前序列] 存在:
            map[当前序列] += 1
        否则:
            map[当前序列] = 1
        如果 map[当前序列] == 2:
            result.add(node)
        返回 当前序列
    调用 serialize(root)
    返回 result

第七步：复杂度分析

时间复杂度：O(N)，每个节点访问一次，字符串拼接总长度与节点数成线性关系（如果使用字符串不可变特性，可能需要优化，但通常可接受）。
空间复杂度：O(N)，用于存储哈希表和递归栈。

第八步：优化方向
如果树很大，字符串可能很长，可改用三元组 (左子树ID, 右子树ID, 节点值) 映射到一个唯一整数ID（通过另一个哈希表分配ID），这样键的长度固定，比较更快。这就是“哈希树”的思路，但实现稍复杂。

通过以上步骤，我们就能高效地找出所有重复的子树。

哈希算法题目：寻找重复的子树题目描述给定一棵二叉树，你需要找出所有重复的子树。对于同一类的重复子树，你只需要返回其中任意一棵的根节点即可。两棵二叉树重复是指它们具有相同的结构以及相同的节点值。示例输入：输出：返回两棵重复子树的根节点列表，顺序不限。上例中重复的子树是：和单个节点 4 。解题过程循序渐进讲解第一步：理解问题与目标我们需要找出二叉树中所有结构完全相同的子树，并且每种结构只返回一个代表根节点。难点在于：如何高效地判断两棵子树是否相同？如果对每对子树都进行递归比较，时间复杂度会很高。优化思路：将每棵子树“序列化”成一个唯一的字符串（或其他可哈希的标识），用哈希表存储已出现过的子树结构，从而快速判断重复。第二步：设计子树标识（哈希键）一种常用的方法是：用后序遍历的方式，将子树序列化成字符串。例如，对于一棵子树，我们可以生成一个像 "4,2,1" 这样的字符串（假设我们用后序遍历，并用逗号分隔节点值，空节点可以用特殊符号如 "#" 表示）。具体规则：空节点表示为 "#" 。非空节点生成字符串格式：左子树字符串,右子树字符串,当前节点值。这样，相同结构的子树一定会生成相同的字符串，不同结构的子树几乎不会碰撞（除非刻意构造，但通常可以忽略）。第三步：遍历树并构建哈希表我们使用深度优先搜索（后序遍历）访问每个节点：如果节点为空，返回 "#" 。递归得到左子树的序列化字符串，再递归得到右子树的序列化字符串。将当前子树序列化为：左字符串 + "," + 右字符串 + "," + 节点值。在哈希表（ HashMap<String, Integer> ）中记录这个字符串出现的次数。如果某个字符串出现次数刚好为 2（表示第二次遇到），就将当前节点加入结果列表（避免重复添加多次）。第四步：示例推导以上面的示例树为例，我们模拟后序遍历过程：节点 4 （左下方的叶子）：左空、右空，序列化： "#,#,4" 。哈希表记录： "#,#,4" 出现 1 次。节点 2 （左下方的那个）：左子树是 "#,#,4" ，右空，序列化： "#,#,4,#,2" 。记录出现 1 次。节点 4 （中间的叶子）： "#,#,4" ，这是第二次出现 "#,#,4" ，次数变为 2，所以将节点 4 加入结果。节点 2 （右子树中的那个）：左子树 "#,#,4" ，右空，序列化： "#,#,4,#,2" ，这是第二次出现这个字符串，所以将节点 2 加入结果。继续遍历其他节点，但没有新的重复了。最终结果包含两个节点：值为 4 的叶子节点（代表单节点子树），和值为 2 的节点（代表结构 (4) 的子树）。第五步：实现细节我们可以用一个 List<TreeNode> 存放结果，用 Map<String, Integer> 记录每个序列化字符串的出现次数。递归函数返回当前子树的序列化字符串。注意：因为字符串拼接可能比较耗时，也可以考虑用唯一ID（如给每个不同的序列分配一个数字ID）来优化，但字符串方法更直观。第六步：伪代码第七步：复杂度分析时间复杂度：O(N)，每个节点访问一次，字符串拼接总长度与节点数成线性关系（如果使用字符串不可变特性，可能需要优化，但通常可接受）。空间复杂度：O(N)，用于存储哈希表和递归栈。第八步：优化方向如果树很大，字符串可能很长，可改用三元组 (左子树ID, 右子树ID, 节点值) 映射到一个唯一整数ID（通过另一个哈希表分配ID），这样键的长度固定，比较更快。这就是“哈希树”的思路，但实现稍复杂。通过以上步骤，我们就能高效地找出所有重复的子树。