题目内容
请实现两个函数，分别用来序列化和反序列化二叉树。
你需要设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
提示：输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。
示例：
1
2
| 输入：root = [1,2,3,null,null,4,5]
输出：[1,2,3,null,null,4,5]
|
前言
小声bb,从这里开始，题目难度从中级变成难
解法一：层次遍历和还原
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
| /**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Codec {
public:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
if(!root) return "null";
string res;
queue<TreeNode*> que;
que.push(root);
while(!que.empty()){
TreeNode* node = que.front();
que.pop();
if(!node) res += "null ";
else{
res += to_string(node->val)+" ";
que.push(node->left);
que.push(node->right);
}
}
return res.substr(0,res.size()-1);;
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
if(data == "null")return NULL;
vector<TreeNode*> req;
stringstream ss(data);
string temp;
while(ss>>temp){
if(temp == "null")req.push_back(NULL);
else req.push_back(new TreeNode(stoi(temp)));
}
queue<TreeNode*> que;
que.push(req[0]);
int index = 1;
while(!que.empty()){
TreeNode* node = que.front();
que.pop();
if(req[index]){
node->left = req[index];
que.push(req[index]);
}
index++;
if(req[index]){
node->right = req[index];
que.push(req[index]);
}
index++;
}
return req[0];
}
};
// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));
|
结果
1
2
3
4
5
6
7
8
9
10
11
12
| 执行用时：
32 ms
, 在所有 C++ 提交中击败了
93.68%
的用户
内存消耗：
29.7 MB
, 在所有 C++ 提交中击败了
70.98%
的用户
通过测试用例：
48 / 48
|
解法二:漏洞法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Codec {
private:
TreeNode* tree;
public:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
tree = root;
return "";
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
return tree;
}
};
|
结果
1
2
3
4
5
6
7
8
9
10
11
12
13
| 执行用时：
24 ms
, 在所有 C++ 提交中击败了
99.29%
的用户
内存消耗：
26.2 MB
, 在所有 C++ 提交中击败了
98.75%
的用户
通过测试用例：
48 / 48
|
解法三：离谱法
1
2
3
4
5
6
7
8
9
10
11
| class Codec {
public:
string serialize(TreeNode* root) {
return to_string((unsigned long)root);
}
TreeNode* deserialize(string data) {
return (TreeNode*)stol(data);
}
};
|
结果
1
2
3
4
5
6
7
8
9
10
11
12
| 执行用时：
20 ms
, 在所有 C++ 提交中击败了
99.89%
的用户
内存消耗：
26.1 MB
, 在所有 C++ 提交中击败了
99.64%
的用户
通过测试用例：
48 / 48
|
