一、题目描述
JZ61序列化二叉树
题目描述：请实现两个函数，分别用来序列化和反序列化二叉树，不对序列化之后的字符串进行约束，但要求能够根据序列化之后的字符串重新构造出一棵与原二叉树相同的树。二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树等遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#），以 ！ 表示一个结点值的结束（value!）。二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。
二、算法1（先序遍历）
解题思路
- 审题过后我们可以发现本题是比较开放的，它对序列化后的字符串没有约束，只要能够还原出原二叉树即可，而要用字符串表示一棵二叉树，自然就联想到了二叉树的遍历
- 根据题目提示，我们可以使用先序遍历的方式序列化二叉树，用
'#'表示空，'!'标志一个结点值的结束，序列化时通过先序遍历的顺序，当遇到非空节点时取出其值的字符串表示再在后面加个'!'标示着结尾，以便我们反序列化时确定节点的值 - 出于代码编写的遍历，我们先用string得到序列，再转换为题目要求的char*字符串；在反序列化时使用引用的下标实时指向当前待处理的位置
代码实现（C++11）
class Solution {
public:
void inorder(TreeNode *root, string& ret){ // 注意这里的ret要使用&
if(root == nullptr){ // 若为空节点用'#'表示
ret += "#";
return;
}
ret += to_string(root->val) + "!"; // "val" + "!"
inorder(root->left, ret); // 先遍历左儿子
inorder(root->right, ret); // 在遍历右儿子
}
char* Serialize(TreeNode *root) {
string ret;
inorder(root, ret);
char* ans = new char[ret.size() + 1]; // 分配内存空间
strcpy(ans, ret.c_str()); // c_str返回c风格的字符串
return ans; // 返回c风格的字符串
}
TreeNode* deserialize(char *str, int& p){
if(str[p] == '#'){ // 若为'#'，返回空指针
++p; // 记住要向后走一步
return nullptr;
}
bool sign = 1; // sign标志当前结点的正负
if(str[p] == '-') sign = 0, ++p; // 若有符号，标记并向后走一步
int val = 0; // 当前结点的绝对值
while(str[p] != '!'){ // 直到遇到结束符号，一直向后走
val = val * 10 + str[p] - '0';
++p;
}
if(!sign) val = -val; // 若为负，更改val符号
++p; // 记住要向后走一步，此时str[p] == '!'
TreeNode* root = new TreeNode(val); // 创建二叉树结点
root->left = deserialize(str, p); // 向左递归
root->right = deserialize(str, p); // 向右递归
return root; // 返回根节点
}
TreeNode* Deserialize(char *str) {
int p = 0; // 指向str中待处理的位置
return deserialize(str, p);
}
}; 时间复杂度：O(n), n为节点数，执行一次先序遍历的时间复杂度为O(n)
空间复杂度：O(n), 节点数为n, 每个结点所占的字符数为常数，故使用的空间是O(n)的，当然还要算上递归使用的栈空间，也是O(n)的
三、算法2（层序遍历）
解题思路
- 序列化：采用与谦虚遍历相似的做法，用
'!'标示数值的结束，用'#'标示空节点，序列化的过程很简单，用队列完成层序遍历，先将根节点入队，然后每次出队一个元素就尝试将其左右儿子加入队列，若无就在字符串后加上'#'，否则加上"val" + "!"即可 - 反序列化：反序列化就是一个层序遍历的逆过程，我们先对序列化的字符串做一下预处理，根据
'!'对每个结点进行分割，用一个vector来存储每个结点所对应的字符串，然后就可以开始层序遍历了。首先将根节点入队，然后每次尝试从vector中取出来个节点，若不为空，则创建节点后入队，以此类推知道遍历完字符串即完成反序列化 - 为了方便代码实现，我们中间采用C++的string，最后转换为C风格字符串即可
代码实现（C++11）
class Solution {
public:
char* Serialize(TreeNode *root) {
string ret;
if(!root) return nullptr;
queue<TreeNode*> q;
q.emplace(root); // 根结点入队
ret += to_string(root->val) + '!'; // 记录节点值
while(q.size()){
TreeNode* p = q.front(); q.pop(); // 队头出队
if(p->left){ // 若不为空，加上"val" + "!"
ret += to_string(p->left->val) + '!';
q.emplace(p->left);
}
else ret += '#'; // 为空这加上'#'
if(p->right){
ret += to_string(p->right->val) + '!';
q.emplace(p->right);
}
else ret += '#';
}
char* ans = new char[ret.size() + 1];
strcpy(ans, ret.c_str());
return ans;
}
TreeNode* Deserialize(char *str) {
if(!str) return nullptr;
string data = string(str);
vector<string> vec; // 先对data预处理一下
for(int i = 0; i < data.size(); i++){
if(data[i] == '#') vec.push_back(string("#")); // 为空则用"#"表示
else{
int j = i;
while(data[j] != '!') ++j;
vec.push_back(data.substr(i, j - i)); // 不为空则用"val"表示
i = j;
}
}
// stoi()函数可以将string转换为int
TreeNode* root = new TreeNode(stoi(vec[0])); // 创建根节点
queue<TreeNode*> q;
q.emplace(root); // 根节点入队
int k = 1;
while(k < vec.size()){
TreeNode* p = q.front(); q.pop();
TreeNode *l = nullptr, *r = nullptr;
if(vec[k] != "#"){ // 若左儿子非空
l = new TreeNode(stoi(vec[k]));
q.emplace(l);
}
p->left = l;
if(vec[k + 1] != "#"){ // 若右儿子非空
r = new TreeNode(stoi(vec[k + 1]));
q.emplace(r);
}
p->right = r;
k += 2; // 指针向后后移动两步
}
return root;
}
}; 时间复杂度：O(n), n为节点数，层序遍历一次的时间复杂度为O(n)
空间复杂度：O(n), 序列化使用了一个队列，反序列化使用了一个vector，故时间复杂度为O(n)
京公网安备 11010502036488号