297

Posted on Edited on In , Views:

題目:
https://leetcode.com/problems/serialize-and-deserialize-binary-tree/

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
// 先序遍歷方式
class Codec {
public:

    string str;
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        str = "";
        serial(root);
        return str;
    }

    void serial(TreeNode* root){
        if(root == nullptr){
            str.append("#,");
            return;
        }
        str.append(to_string(root->val)).append(",");
        serial(root->left);
        serial(root->right);
    }

    vector<string> result;
    string tmp;
    int cnt;
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        tmp = "";
        cnt = 0;
        stringstream ss(data);
        while(getline(ss, tmp, ',')){ // equivalent to .split(",") method in Java
            result.push_back(tmp);
        }
        return deserial();
    }

    TreeNode* deserial(){
        string curr = result[cnt++];
        if(curr == "#") return nullptr;
        TreeNode* head = new TreeNode(stoi(curr));
        head->left = deserial();
        head->right = deserial();
        return head;
    }
};

// 按層遍歷(BFS)方式
#define MAXN 10005

TreeNode* q[MAXN];
int l, r;

class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string serial = "";
        if(root == nullptr) return serial;
        l = r = 0;
        q[r++] = root;
        serial.append(to_string(root->val)).append(",");
        while(l < r){
            TreeNode* curr = q[l++];

            if(curr->left == nullptr) serial.append("#,");
            else{
                serial.append(to_string(curr->left->val)).append(",");
                q[r++] = curr->left;
            }

            if(curr->right == nullptr) serial.append("#,");
            else{
                serial.append(to_string(curr->right->val)).append("#,");
                q[r++] = curr->right;
            }
        }
        return serial;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if(data == "") return nullptr;
        l = r = 0; // queue
        int index = 0; // nodes

        vector<string> nodes;
        string tmp;
        stringstream ss(data);
        while(getline(ss, tmp, ',')){
            nodes.push_back(tmp);
        }

        q[r++] = generate(nodes[index++]);
        while(l < r){
            TreeNode* curr = q[l++];
            curr->left = generate(nodes[index++]);
            curr->right = generate(nodes[index++]);
            if(curr->left != nullptr) q[r++] = curr->left;
            if(curr->right != nullptr) q[r++] = curr->right;
        }
        return q[0];
    }

    TreeNode* generate(string node){
        return node == "#" ? nullptr : new TreeNode(stoi(node));
    }
};