leetcode/652. Find Duplicate Subtrees.cpp at main · Heepo/leetcode · GitHub

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <vector>
#include <unordered_map>
#include <string>
using namespace std;

// 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) {}
};

// serializes every subtree and counts it in a hashtable
// T: O(n^2)
// S: O(n^2)
class Solution {
public:
    vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
        if (!root) return {};

        vector<TreeNode*> ans;
        unordered_map<std::string, int> count;
        serialize_(root, count, ans);

        return ans;
    }

private:
    std::string serialize_(TreeNode* cur, unordered_map<std::string, int>& count, vector<TreeNode*>& ans) {
        if (!cur) return "#";

        // O(n)
        std::string key = std::to_string(cur->val) + "," + serialize_(cur->left, count, ans) + "," + serialize_(cur->right, count, ans);

        if (++count[key] == 2) ans.push_back(cur);

        return key;
    }
};


// T: O(n)
// S: O(n)
class Solution2 {
public:
    vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
        if (!root) return {};

        vector<TreeNode*> ans;
        unordered_map<long, int> id_m;
        unordered_map<int, int> id_count;
        assign_id_(root, id_m, id_count, ans);

        return ans;
    }

private:
    int assign_id_(TreeNode* cur, unordered_map<long, int>& id_m, unordered_map<int, int>& id_count, vector<TreeNode*>& ans) {
        if (!cur) return 0;

        // traversal time O(n), id assignment O(1)
        // Assuming the unique node number is under 65536
        long key = (static_cast<long>(static_cast<unsigned int>(cur->val)) << 32) | (assign_id_(cur->left, id_m, id_count, ans) << 16) | assign_id_(cur->right, id_m, id_count, ans);
        int id = id_m.count(key) ? id_m[key] : (id_m.size() + 1);
        id_m[key] = id;

        if (++id_count[id] == 2) ans.push_back(cur);

        return id;
    }
};