寻找重复的子树

题目描述

给定一棵二叉树的根节点 root，你需要找出所有重复的子树。这里的“重复”是指存在两棵或多棵子树具有完全相同的结构和节点值。你需要以列表的形式返回所有这些重复子树的根节点。

示例

假设有这样一棵二叉树：

        1
       / \
      2   3
     /   / \
    4   2   4
       /
      4

在这棵树中，子树 [2, 4] 和 [4] 出现了多次。具体来说：

• 以节点 2（值为2，左孩子为4）为根的子树 [2, 4] 出现了两次。
• 以叶子节点 4 为根的子树 [4] 出现了三次。

因此，我们需要返回这些重复子树的根节点。注意，对于多次出现的子树，我们只需要返回其中任意一个根节点即可。

解题思路

1. 核心挑战：如何高效地判断两棵子树是否完全相同？
2. 直觉想法：如果我们能有一种方法，将一棵子树“编码”成一个唯一的标识符（例如一个字符串），那么判断两棵子树是否相同，就变成了判断它们的标识符是否相同。
3. 关键工具：哈希表。我们可以使用一个哈希表（在Python中是字典dict）来记录每个子树标识符出现的次数。
4. 算法选择：后序遍历。为了序列化一棵子树，我们需要知道它的左子树和右子树长什么样。这正好符合后序遍历（左 -> 右 -> 根）的顺序。当我们遍历到一个节点时，它的左右子树已经被序列化好了。
5. 序列化方法：我们将一棵子树序列化为一个字符串，格式可以自定义，例如 左子树序列化结果,当前节点值,右子树序列化结果。为了处理空节点，我们用特殊字符（如#）表示。

循序渐进讲解

步骤 1：设计序列化方案

我们决定使用后序遍历来序列化子树。序列化格式约定如下：

• 空节点用 "#" 表示。
• 非空节点的序列化字符串为：左子树序列化结果 + "," + 右子树序列化结果 + "," + str(当前节点值)。
• 注意：这里我们使用后序遍历，所以顺序是左,右,根。将节点值放在最后，可以确保序列化字符串的唯一性。

例如，一个单独的节点 4 会被序列化为 "#,#,4"。
一棵子树 [2, 4]（节点2的左孩子是4）会被序列化为：首先序列化左子树4得到"#,#,4"，序列化右子树（空）得到"#"，然后组合："#,#,4" + "," + "#" + "," + "2"，即 "#,#,4,#,2"。

步骤 2：使用哈希表进行计数

我们创建一个全局的（或在递归中传递的）字典 count_map，它的键是子树的序列化字符串，值是该序列化字符串出现的次数。

同时，我们创建一个结果列表 result，用于存放重复子树的根节点。

步骤 3：递归遍历与序列化（后序遍历）

我们编写一个递归函数 traverse(node)：

1. 基准情况：如果当前节点 node 为空，返回代表空节点的字符串，例如 "#"。
2. 递归序列化左子树：left_str = traverse(node.left)
3. 递归序列化右子树：right_str = traverse(node.right)
4. 构建当前子树的序列化字符串：serial = left_str + "," + right_str + "," + str(node.val)
5. 更新哈希表：
   • 在 count_map 中查找键 serial。
   • 如果不存在，则 count_map[serial] = 1。
   • 如果存在，则 count_map[serial] += 1。
6. 检查是否重复：如果 count_map[serial] == 2，说明这个序列化字符串是第二次出现，意味着我们找到了一个重复的子树。此时，我们将当前节点 node 加入到结果列表 result 中。（为什么是等于2？因为等于2是第一次发现重复，之后如果再出现（3,4,...次），我们就不再添加了，避免结果列表中出现同一个子树的多个根节点）。
7. 返回序列化字符串：将 serial 返回给上一级调用。

步骤 4：启动递归并返回结果

从根节点开始调用 traverse(root)。遍历结束后，返回结果列表 result。

完整过程模拟（以示例二叉树为例）

树结构：

        1
       / \
      2   3
     /   / \
    4   2   4
       /
      4

1. 遍历节点4（最左边的叶子）：

   • 左子树序列化："#"
   • 右子树序列化："#"
   • 序列化结果："#,#,4"
   • count_map["#,#,4"] 变为 1。
   • 返回 "#,#,4"。

2. 遍历节点2（值为2，左孩子是刚才的节点4）：

   • 左子树序列化："#,#,4" (来自步骤1)
   • 右子树序列化："#"
   • 序列化结果："#,#,4,#,2"
   • count_map["#,#,4,#,2"] 变为 1。
   • 返回 "#,#,4,#,2"。

3. 遍历根节点1的左子树（节点2）完成。

4. 遍历节点4（中间的那个叶子，节点3的左子树的左孩子）：

   • 序列化结果："#,#,4"
   • count_map["#,#,4"] 变为 2。发现重复！ 将这个节点4加入 result。
   • 返回 "#,#,4"。

5. 遍历节点2（节点3的左孩子）：

   • 左子树序列化："#,#,4" (来自步骤4)
   • 右子树序列化："#"
   • 序列化结果："#,#,4,#,2"
   • count_map["#,#,4,#,2"] 变为 2。发现重复！ 将这个节点2加入 result。
   • 返回 "#,#,4,#,2"。

6. 遍历节点4（节点3的右孩子）：

   • 序列化结果："#,#,4"
   • count_map["#,#,4"] 变为 3。（已经大于2，不重复添加节点到结果）
   • 返回 "#,#,4"。

7. 遍历节点3：

   • 左子树序列化："#,#,4,#,2" (来自步骤5)
   • 右子树序列化："#,#,4" (来自步骤6)
   • 序列化结果："#,#,4,#,2,#,#,4,3"
   • count_map["#,#,4,#,2,#,#,4,3"] 变为 1。
   • 返回该字符串。

8. 遍历根节点1：

   • 左子树序列化："#,#,4,#,2" (来自步骤2)
   • 右子树序列化："#,#,4,#,2,#,#,4,3" (来自步骤7)
   • 序列化结果："#,#,4,#,2,#,#,4,#,2,#,#,4,3,1" (一个很长的字符串)
   • count_map 对应计数加1。
   • 返回该字符串。

9. 最终结果：result 列表中包含了在步骤4和步骤5中添加的节点，即两个重复子树的根节点：一个值为4的叶子节点，和一个值为2的非叶子节点。

总结

通过将子树序列化为字符串，并利用哈希表记录出现次数，我们巧妙地将在树中寻找结构重复的问题，转化为了在哈希表中判断字符串重复的问题。后序遍历确保了我们在序列化一个节点时，其左右子树的信息已经准备就绪。这种方法的时间复杂度和空间复杂度均为 O(N)，其中 N 是树中的节点数。