题目简介：
序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。
请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
示例:
1
2
3
4
5
6
7
8
| 你可以将以下二叉树：
1
/ \
2 3
/ \
4 5
序列化为 "[1,2,3,null,null,4,5]"
|
提示: 这与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。
说明: 不要使用类的成员 / 全局 / 静态变量来存储状态，你的序列化和反序列化算法应该是无状态的。
思路：
序列化时，利用队列进行BFS，将每个结点对应的值(value)存入字符串中，若遇到NULL，则存入N，每个结点间用空格分隔。
反序列化时，利用双指针分别指向一个数字(value)的开始和末尾，来确定一个数，需要注意遇到N和负数的情况，把每次的value构成一个结点，存入vector中。
最后将vector中的值依次拿出来构建成树，注意具体的代码实现。
代码如下：
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
|
class Codec {
public:
string serialize(TreeNode* root) {
string res;
queue<TreeNode*> qu;
qu.push(root);
while(!qu.empty()){
TreeNode* node = qu.front();
if(node){
res += to_string(node -> val);
res += " ";
qu.push(node -> left);
qu.push(node -> right);
}
else{
res += "N";
res += " ";
}
qu.pop();
}
return res;
}
TreeNode* deserialize(string data) {
if(data.length() == 0)
return NULL;
vector<TreeNode*> valList;
for(int left = 0, right = 1; left < data.size(); ){
while(data[right] != ' ')
right++;
if(data[left] == 'N'){
left = right + 1;
right = left;
valList.push_back(NULL);
continue;
}
int val = 0;
int sign = 1;
if(data[left] == '-'){
left++;
sign = -1;
}
for(int i = left; i < right; i++){
val = val * 10 + data[i] - '0';
}
val = val * sign;
TreeNode* node = new TreeNode(val);
valList.push_back(node);
left = right + 1;
right = left;
}
TreeNode* root = valList[0];
TreeNode* nownode = root;
for(int i = 1, j = 0; i < valList.size() && j < valList.size(); ){
if(!nownode){
j++;
nownode = valList[j];
continue;
}
nownode -> left = valList[i];
nownode -> right = valList[i + 1];
i += 2;
j++;
nownode = valList[j];
}
return root;
}
};
|
