序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。
请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
提示: 输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。
示例 1：
**输入：**root = [1,2,3,null,null,4,5]
输出：[1,2,3,null,null,4,5]
示例 2：
**输入：**root = []
输出：[]
示例 3：
**输入：**root = [1]
输出：[1]
示例 4：
**输入：**root = [1,2]
输出：[1,2]
提示：
树中结点数在范围 [0, 10(4)] 内
-1000 <= Node.val <= 1000
将二叉树抽象出来再还原，之前我们通过前序和中序遍历结果还原出二叉树
为了能获取完整的二叉树信息，我们可以把null结点也打印出来，这样我们在还原时能方便的得出哪个结点是叶子结点
下面分别是通过前序遍历和层序遍历的序列化写法
后序遍历就是还原时倒序读入即可，中序遍历无法判断根节点位置
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
| TypeScript class Codec {
public:
void dfs(TreeNode *cur, string &str) {
if (cur == NULL) {
str += "# ";
return;
}
str += to_string(cur->val) + " ";
dfs(cur->left, str);
dfs(cur->right, str);
}
string serialize(TreeNode *root) {
string res;
dfs(root, res);
return res;
}
TreeNode *build(queue<string> &seria) {
if (seria.front() == "#") {
seria.pop();
return NULL;
}
int val = stoi(seria.front());
TreeNode *root = new TreeNode(val);
seria.pop();
root->left = build(seria);
root->right = build(seria);
return root;
}
TreeNode *deserialize(string data) {
queue<string> seria;
string mid;
for (char c : data) {
if (c == ' ' && !mid.empty()) {
seria.push(mid);
mid.clear();
} else
mid += c;
}
return build(seria);
}
};
|
层序遍历
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
| class Codec {
public:
string serialize(TreeNode *root) {
if (!root)
return "# ";
string res = "";
queue<TreeNode *> q;
q.push(root);
while (!q.empty()) {
TreeNode *cur = q.front();
q.pop();
if (cur == nullptr) {
res += "# ";
continue;
}
res += to_string(cur->val) + " ";
q.push(cur->left);
q.push(cur->right);
}
return res;
}
TreeNode *deserialize(string data) {
if (data == "# " || data.empty())
return nullptr;
stringstream ss(data);
string val;
ss >> val;
TreeNode *root = new TreeNode(stoi(val));
queue<TreeNode *> q;
q.push(root);
while (!q.empty()) {
TreeNode *cur = q.front();
q.pop();
if (!(ss >> val))
break;
if (val != "#") {
cur->left = new TreeNode(stoi(val));
q.push(cur->left);
}
if (!(ss >> val))
break;
if (val != "#") {
cur->right = new TreeNode(stoi(val));
q.push(cur->right);
}
}
return root;
}
};
|
