Skip to content

树哈希

652. 寻找重复的子树

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

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

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

方法一

将每一颗子树都序列化为一个字符串，并且： 1. 相同子树序列化成相同的字符串 2. 不同子树序列化为不同的字符串

也就是说，一个序列化后的字符串可以唯一指定一个树。这样用哈希表去存储字符串，就可以方便查找是否存在相同的子树。

常用的序列化方法：

  1. 层序遍历法，具体请参考 LC297.二叉树的序列化与反序列化
  2. 递归表示法：x(左子树序列化结果)(右子树序列化结果)

这里我使用层序遍历法，结构表示为 x,左子树序列化结果,右子树序列化结果,。

时间复杂度 \(O(n^2)\)，空间复杂度 \(O(n^2)\)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
        dfs(root);
        return {res.begin(), res.end()};
    }
    string dfs(TreeNode* root) {
        if(root == nullptr) return " ";
        string s = to_string(root->val) + "," + dfs(root->left) + "," + dfs(root->right);
        if(auto it = mp.find(s); it != mp.end()) {
            // 注意此处并不能将 root 放入 res
            res.insert(it->second);
        } else {
            mp[s] = root;
        }
        return s;
    }
private:
    unordered_map<string, TreeNode*> mp;
    unordered_set<TreeNode*> res;
};

方法二

另外一种方法是，对每一个本质不同的子树用一个整数进行编号。然后使用三元组 (根节点值，左子树编号，右子树编号) 即可唯一指定一棵树。

容易想到，如果两个子树 \(root_x\) 和 \(root_y\) 是本质相同的，那么它们左子树和右子树分别对应本质相同，并且根节点值也是相同的。相反，如果两个子树本质不同，那么三元组中的三个元素一定不完全相同。

时间复杂度 \(O(n)\)，空间复杂度 \(O(n)\)

 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
class Solution {
public:
    vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
        idx = 0;
        dfs(root);
        return {res.begin(), res.end()};
    }
    int dfs(TreeNode* root) {
        if(root == nullptr) return 0;
        auto tp = make_tuple(root->val, dfs(root->left), dfs(root->right));
        if(auto it = mp.find(tp); it != mp.end()) {
            res.insert(it->second.first);
            return it->second.second;
        } else {
            mp[tp] = make_pair(root, ++idx);
            return idx;
        }
    }
private:
    // 对三元组编写自定义 hash 函数
    static constexpr auto tuple_hash = [fn = hash<int>()](const tuple<int, int, int> &oth) -> size_t {
        auto&& [x, y, z] = oth;
        return (fn(x) << 24) ^ (fn(y) << 8) ^ fn(z);
    };
    unordered_map<tuple<int, int, int>, pair<TreeNode*, int>, decltype(tuple_hash)> mp{0, tuple_hash};
    unordered_set<TreeNode*> res;
    int idx;
};
本文访问 次