Leetcode652. 寻找重复的子树

题目链接

点我(^_^)

---

题目大意

比如下面的两个子树[2,4,null]属于重复子树，且其子树[4]也是重复子树。
—

解题思路

1. 序列化

序列化可以采用层序遍历的方法进行序列化，例如上图的二叉树可以被序列化为：
1,2,3,4,null,2,4,null,null,4

也可以按照下面递归的方法进行序列化，可以将一棵以 x 为根节点值的子树序列化为：
x(左子树的序列化结果)(右子树的序列化结果)

左右子树分别递归地递归地进行序列化。如果子树为空，那么序列化结果为空串。上图的二叉树可以序列化为：
1(2(4()())())(3(2(4()())(4()()))

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

2. 三元组表示
   序列化的方法其实会有很多冗余的字符，时间复杂度O(n²)如果我们直接使用三元组表示一个树的结构，即用一个独一无二的数字表示一种树结构，那么其也可以被分解为 (l, r, val) l 即左子树结构的对应数字，r 即右子树结构的对应数字，val 即当前节点的数字。我们可以用哈希映射到 seen 存储序列中，如果seen中已经有了，就把对应子树放到哈希集合 repeat 中。

---

代码(C++)

使用递归序列化表示的方式

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

使用三元组表示的方式

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    struct node
    {
        int l, r, val;
        node(int _l, int _r, int _val) : l(_l), r(_r), val(_val) {}
        friend bool operator == (const node &a, const node &b)
        {
            if(a.l==b.l && a.r==b.r && a.val==b.val)
                return true;
            else
                return false;
        }
    };

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

    int dfs(TreeNode* root) {
        if (root == nullptr) {
            return 0;
        }
        node temp(dfs(root->left), dfs(root->right), root->val);
        if(!seen[temp])
        {
            seen[temp] = ++cnt;
            a[cnt] = root;
        }
        else
            repeat.insert(a[seen[temp]]);
        return seen[temp];
    }

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

    unordered_map<node, int, decltype(tri_hash)> seen{0, tri_hash};
    unordered_set<TreeNode*> repeat;
    int cnt = 0;
    TreeNode* a[10005];
};
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57