算法

每日leetcode-297

序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。

请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

示例: 

你可以将以下二叉树：

1

/
2 3
/
4 5

序列化为 “[1,2,3,null,null,4,5]”
提示: 这与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。

说明: 不要使用类的成员 / 全局 / 静态变量来存储状态，你的序列化和反序列化算法应该是无状态的。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

尝试

这道题最先想到的是直接把每一层每一个位置都编码，做成一个堆，这样就可以直接用下标/2得到父亲节点的位置：

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
109
110
111
class Codec {
public:
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        map<int, TreeNode*> nodes;
        nodes[0] = root;
        int len = 1;
        bool now_have_nodes = !!root;
        string ans;
        while (now_have_nodes) {
            for (int i = 0; i < len; i++) {
                if (nodes[i]) {
                    stringstream ss;
                    ss << nodes[i]->val;
                    string temp;
                    ss >> temp;
                    ans += temp + ";";
                }
                else {
                    ans += ";";
                }
            }
            now_have_nodes = false;
            for (int i = len - 1; i >= 0; i--) {
                if (nodes[i]) {
                    if (nodes[i]->left || nodes[i]->right) {
                        now_have_nodes = true;
                    }
                    nodes[2 * i + 1] = nodes[i]->right;
                    nodes[2 * i] = nodes[i]->left;
                }
                else {
                    nodes[2 * i] = NULL;
                    nodes[2 * i + 1] = NULL;
                }
            }
            len *= 2;
        }
        return ans;
    }

    int readNumber(const string & data, const int len, int & now_char_index, bool & now_have_number) {
        now_have_number = false;
        int now_data = 0;
        bool negative = false;
        if (data[now_char_index] == '-') {
            negative = true;
            now_char_index ++;
        }
        while (now_char_index < len) {
            if (data[now_char_index] >= '0' && data[now_char_index] <= '9') {
                now_data = now_data * 10 + data[now_char_index] - '0';
                now_have_number = true;
                now_char_index++;
            }
            else if (data[now_char_index] == ';') {
                now_char_index++;
                break;
            }
            else {
                now_char_index++;
            }
        }
        return negative ? -now_data : now_data;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        int len = data.size();
        int now_char_index = 0;  // 当前的字符串字符的下标
        int now_level_size = 1;  // 当前这一层的节点一共有多少个
        int now_data = 0;  // 当前的读取的数字
        bool now_have_number = false;
        if (len == 0) {
            return NULL;
        }
        map<int, TreeNode*> nodes;
        map<int, TreeNode*> nodes2;
        now_data = readNumber(data, len, now_char_index, now_have_number);
        if (!now_have_number) {
            return NULL;
        }
        TreeNode* ans = new TreeNode(now_data);
        nodes[0] = ans;
        // 读入下面一层的
        while (now_char_index < len) {
            now_level_size *= 2;
            int now_node_index = 0;
            while (now_node_index < now_level_size) {
                now_data = readNumber(data, len, now_char_index, now_have_number);
                if (now_have_number) {
                    nodes2[now_node_index] = new TreeNode(now_data);
                }
                else {
                    nodes2[now_node_index] = NULL;
                }
                if (nodes[now_node_index / 2]) {
                    if (now_node_index % 2 == 0) {
                        nodes[now_node_index / 2]->left = nodes2[now_node_index];
                    }
                    else {
                        nodes[now_node_index / 2]->right = nodes2[now_node_index];
                    }
                }
                now_node_index++;
            }
            nodes = nodes2;
        }
        return ans;
    }
};

但是这样会超时，因为这样做的话比如

1

/
3
/
4 5

就会被写成”1;;3;;;4;5;”，但是第三层前两个空的节点是没有必要存下来的。

解决

所以修改存储的方式：

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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
class Codec {
public:
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        vector<TreeNode*> nodes;
        nodes.push_back(root);
        int len;
        bool now_have_nodes = !!root;
        string ans;
        while (now_have_nodes) {
            len = nodes.size();
            for (int i = 0; i < len; i++) {
                if (nodes[i]) {
                    stringstream ss;
                    ss << nodes[i]->val;
                    string temp;
                    ss >> temp;
                    ans += temp + ";";
                }
                else {
                    ans += ";";
                }
            }
            now_have_nodes = false;
            vector<TreeNode*> nodes2;
            for (int i = 0; i < len; i++) {
                if (nodes[i]) {
                    if (nodes[i]->left || nodes[i]->right) {
                        now_have_nodes = true;
                    }
                    nodes2.push_back(nodes[i]->left);
                    nodes2.push_back(nodes[i]->right);
                }
            }
            nodes = nodes2;
        }
        return ans;
    }

    int readNumber(const string & data, const int len, int & now_char_index, bool & now_have_number) {
        now_have_number = false;
        int now_data = 0;
        bool negative = false;
        if (data[now_char_index] == '-') {
            negative = true;
            now_char_index ++;
        }
        while (now_char_index < len) {
            if (data[now_char_index] >= '0' && data[now_char_index] <= '9') {
                now_data = now_data * 10 + data[now_char_index] - '0';
                now_have_number = true;
                now_char_index++;
            }
            else if (data[now_char_index] == ';') {
                now_char_index++;
                break;
            }
            else {
                now_char_index++;
            }
        }
        return negative ? -now_data : now_data;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        int len = data.size();
        int now_char_index = 0;  // 当前的字符串字符的下标
        int now_data = 0;  // 当前的读取的数字
        bool now_have_number = false;
        if (len == 0) {
            return NULL;
        }
        vector<TreeNode*> nodes;
        now_data = readNumber(data, len, now_char_index, now_have_number);
        if (!now_have_number) {
            return NULL;
        }
        TreeNode* ans = new TreeNode(now_data);
        nodes.push_back(ans);
        int len_n = 1;
        // 读入下面一层的
        while (now_char_index < len) {
            vector<TreeNode*> nodes2;
            int parent_index = 0;
            while (parent_index < len_n) {
                if (!nodes[parent_index]) {
                    parent_index ++;
                }
                else {
                    break;
                }
            }
            for (int i = 0; parent_index < len_n; i++) {
                while (parent_index < len_n) {
                    if (!nodes[parent_index]) {
                        parent_index ++;
                    }
                    else {
                        break;
                    }
                }
                if (parent_index >= len_n) {
                    break;
                }
                now_data = readNumber(data, len, now_char_index, now_have_number);
                TreeNode* now_node = NULL;
                if (now_have_number) {
                    now_node = new TreeNode(now_data);
                }
                nodes2.push_back(now_node);
                if (i % 2 == 0) {
                    nodes[parent_index]->left = now_node;
                }
                else {
                    nodes[parent_index]->right = now_node;
                    parent_index += 1;
                }
            }
            nodes = nodes2;
            len_n = nodes.size();
            if (len_n == 0) {
                break;
            }
        }
        return ans;
    }
};

这样可以通过，但是时间不是最优。

最优

看到的一个20ms的提交代码，使用queue，避免了我刚才用vector的复制操作；用换行作为分隔符，直接就可以用getline读取：

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
class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        queue<TreeNode *> q;
        q.push(root);
        ostringstream oss;
        while(!q.empty()) {
            TreeNode *cur = q.front();
            q.pop();
            if(cur == nullptr) {
                oss << "null" << endl;
            } else {
                oss << cur->val << endl;
                q.push(cur->left);
                q.push(cur->right);
            }
        }
        // cout << oss.str();
        return oss.str();
    }

    TreeNode *decodeNode(const string &data) {
        if(data == "null")
            return nullptr;
        else
            return new TreeNode(stoi(data.c_str()));
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        string buffer;
        istringstream iss(data);
        TreeNode *root;
        getline(iss, buffer);
        root = decodeNode(buffer);
        if(root == nullptr)
            return root;
        queue<TreeNode *> q;
        q.push(root);
        while(!q.empty()) {
            TreeNode *cur = q.front();
            q.pop();
            getline(iss, buffer);
            cur->left = decodeNode(buffer);
            getline(iss, buffer);
            cur->right = decodeNode(buffer);
            if(cur->left) q.push(cur->left);
            if(cur->right) q.push(cur->right);
        }
        return root;
    }
};