JZ37 序列化二叉树
描述
请实现两个二函数，分别用来序列化和反序列化二叉树，不对序列化之后的字符串进行约束，但要求能够根据序列化之后的字符串重新构造出一棵与原二叉树相同的树。
二叉树的序列化(Serialize)是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树等遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#）
二叉树的反序列化(Deserialize)是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。
例如，可以根据层序遍历的方案序列化，如下图:
1
| 层序序列化(即用函数Serialize转化)如上的二叉树转为{1,2,3,#,#,6,7}，再能够调用反序列化(Deserialize)将{1,2,3,#,#,6,7}构造成如上的二叉树。 再举一个例子
|
1
| 层序序列化(即用函数Serialize转化)如上的二叉树转为{5,4,#,3,#,2}，再能够调用反序列化(Deserialize)将{5,4,#,3,#,2}构造成如上的二叉树。
|
当然你也可以根据满二叉树结点位置的标号规律来序列化，还可以根据先序遍历和中序遍历的结果来序列化。不对序列化之后的字符串进行约束，所以欢迎各种奇思妙想。
数据范围：节点数$n≤100$，树上每个节点的值满足 $0≤val≤150$
要求：序列化和反序列化都是空间复杂度 $O(n)$，时间复杂度 $O(n)$
示例1
1
2
3
| 输入：{1,2,3,#,#,6,7}
返回值：{1,2,3,#,#,6,7}
说明：如题面图
|
示例2
1
2
| 输入：{8,6,10,5,7,9,11}
返回值：{8,6,10,5,7,9,11}
|
题解
初见思路：有一个一定能成的思路就是序列化的话就输出一个中序序列一个前序序列，二者中间使用$\#$分割，在反序列化的时候把这两个序列还原出来，然后再还原树就可以了。
看了一下，大G老师给出的主要也就是两类做法，一类是使用单独的一个遍历序列，但是要把空结点用特殊记号表示；第二类是用两个序列，这样就不用特殊记号来表示了。
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
|
class Solution {
public:
char* Serialize(TreeNode* root) {
if (!root) return nullptr;
stringstream ss;
serializeHelper(root, ss);
string serializedStr = ss.str();
char* result = new char[serializedStr.size() + 1];
strcpy(result, serializedStr.c_str());
return result;
}
TreeNode* Deserialize(char* str) {
if (!str) return nullptr;
stringstream ss(str);
return deserializeHelper(ss);
}
private:
void serializeHelper(TreeNode* root, stringstream& ss) {
if (!root) {
ss << "#" << " ";
return;
}
ss << root->val << " ";
serializeHelper(root->left, ss);
serializeHelper(root->right, ss);
}
TreeNode* deserializeHelper(stringstream& ss) {
string val;
ss >> val;
if (val == "#") return nullptr;
TreeNode* node = new TreeNode(stoi(val));
node->left = deserializeHelper(ss);
node->right = deserializeHelper(ss);
return node;
}
};
|
