【652. 寻找重复的子树】

来源：力扣（LeetCode）

描述：

给定一棵二叉树 root，返回所有重复的子树。

对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。

如果两棵树具有相同的结构和相同的结点值，则它们是重复的。

示例 1：

输入：root = [1,2,3,4,null,2,4,null,null,4]
输出：[[2,4],[4]]
1
2

示例 2：

输入：root = [2,1,1]
输出：[[1]]
1
2

示例 3：

输入：root = [2,2,2,3,null,3,null]
输出：[[2,3],[3]]
1
2

提示：

• 树中的结点数在[1,10⁴]范围内。

• -200 <= Node.val <= 200

方法一：使用序列化进行唯一表示

思路与算法

一种容易想到的方法是将每一棵子树都「序列化」成一个字符串，并且保证：

相同的子树会被序列化成相同的子串；
不同的子树会被序列化成不同的子串。
那么我们只要使用一个哈希表存储所有子树的序列化结果，如果某一个结果出现了超过一次，我们就发现了一类重复子树。

这里也给出两种常用的序列化方法：

• 第一种方法是使用层序遍历的方法进行序列化，例如示例 1中的二叉树可以序列化为：

1,2,3,4,null,2,4,null,null,4

这也是力扣平台上测试代码时输入一棵二叉树的默认方法。

• 第二种方法是使用递归的方法进行序列化。我们可以将一棵以 x 为根节点值的子树序列化为：

x(左子树的序列化结果)(右子树的序列化结果)

左右子树分别递归地进行序列化。如果子树为空，那么序列化结果为空串。示例 1中的二叉树可以序列化为：

1(2(4()())())(3(2(4()())())(4()()))

下面的代码使用的是第二种方法。我们需要使用一个哈希映射 seen 存储序列到子树的映射。如果在计算序列时，通过 seen 查找到了已经出现过的序列，那么就可以把对应的子树放到哈希集合 repeat 中，这样就可以保证同一类的重复子树只会被存储在答案中一次。

代码：

class Solution {
public:
    vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
        dfs(root);
        return {repeat.begin(), repeat.end()};
    }

    string dfs(TreeNode* node) {
        if (!node) {
            return "";
        }
        string serial = to_string(node->val) + "(" + dfs(node->left) + ")(" + dfs(node->right) + ")";
        if (auto it = seen.find(serial); it != seen.end()) {
            repeat.insert(it->second);
        }
        else {
            seen[serial] = node;
        }
        return serial;
    }

private:
    unordered_map<string, TreeNode*> seen;
    unordered_set<TreeNode*> repeat;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

执行用时：28 ms, 在所有 C++ 提交中击败了88.92%的用户
内存消耗：41.6 MB, 在所有 C++ 提交中击败了87.12%的用户
复杂度分析
时间复杂度：O(n²)，其中 n 是树中节点的数目。在最坏情况下，树呈现链状的结构，而每一个节点都会在其左右子树序列的基础上再增加最多 9 个字符（两组括号以及节点本身的值），那么所有子树的序列长度之和为 ∑ⁿ_i=1 9n=O(n²)。构造出这些序列就需要 O(n²)的时间。
空间复杂度：O(n²)，即为哈希表需要使用的空间。

方法二：使用三元组进行唯一表示

思路与算法

通过方法一中的递归序列化技巧，我们可以进一步进行优化。

我们可以用一个三元组直接表示一棵子树，即 (x, l, r)，它们分别表示：

• 根节点的值为 x；

• 左子树的序号为 l；

• 右子树的序号为 r。

这里的「序号」指的是：每当我们发现一棵新的子树，就给这棵子树一个序号，用来表示其结构。那么两棵树是重复的，当且仅当它们对应的三元组完全相同。

使用「序号」的好处在于同时减少了时间复杂度和空间复杂度。方法一的瓶颈在于生成的序列会变得非常长，而使用序号替换整个左子树和右子树的序列，可以使得每一个节点只使用常数大小的空间。

代码：

class Solution {
public:
    vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
        dfs(root);
        return {repeat.begin(), repeat.end()};
    }

    int dfs(TreeNode* node) {
        if (!node) {
            return 0;
        }
        auto tri = tuple{node->val, dfs(node->left), dfs(node->right)};
        if (auto it = seen.find(tri); it != seen.end()) {
            repeat.insert(it->second.first);
            return it->second.second;
        }
        else {
            seen[tri] = {node, ++idx};
            return idx;
        }
    }

private:
    static constexpr auto tri_hash = [fn = hash<int>()](const tuple<int, int, int>& o) -> size_t {
        auto&& [x, y, z] = o;
        return (fn(x) << 24) ^ (fn(y) << 8) ^ fn(z);
    };

    unordered_map<tuple<int, int, int>, pair<TreeNode*, int>, decltype(tri_hash)> seen{0, tri_hash};
    unordered_set<TreeNode*> repeat;
    int idx = 0;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

执行用时：20 ms, 在所有 C++ 提交中击败了98.69%的用户
内存消耗：26.7 MB, 在所有 C++ 提交中击败了98.90%的用户
复杂度分析
时间复杂度： O(n)，其中 n 是树中节点的数目。
空间复杂度： O(n)，即为哈希表需要使用的空间。
author：LeetCode-Solution