方法一：递归
1.解题思路
题意：
二叉树的序列化：给定二叉树，将其结点的遍历序列保存下来，可用前序/中序/后序/层序，保存为字符串。
二叉树的反序列化：接着利用这个字符串再构建回原来的二叉树。
相关知识：
- 前序遍历模板
void preorder(node* root){
if(root==NULL)return;//到达空树，递归边界
printf("%d\n",root->data);
preorder(root->lchild);//访问左子树
preorder(root->rchild);//访问右子树
}- 中序遍历模板
void inorder(node* root){
if(root==NULL)return;//到达空树，递归边界
inorder(root->lchild);//访问左子树
printf("%d\n",root->data);
inorder(root->rchild);//访问右子树
}- 后序遍历模板
void postorder(node* root){
if(root==NULL)return;//到达空树，递归边界
postorder(root->lchild);//访问左子树
postorder(root->rchild);//访问右子树
printf("%d\n",root->data);
}- 层序遍历模板
struct node{
int data;
int layer;
node* lchild;
node* rchild;
};
void layerorder(node* root){
queue<node*>q;
root->layer=1;
q.push(root);//将根结点地址入队
while(!q.empty()){
node* now=q.front();//取出队首元素
q.pop();
printf("%d",now->data);//访问队首元素
if(now->lchild!=NULL){
now->lchild->layer=now->layer+1;
q.push(now->lchild);}//左子树非空
if(now->rchild!=NULL){
now->rchild->layer=now->layer+1;
q.push(now->rchild);}//右子树非空
}
} 2.解法
序列化：采用递归的方式，将大问题划分成小问题，逐个解决。即先深度优先搜索二叉树得到根结点权值，左右孩子非空的时候再分别加上左右孩子结点权值，再不断递归左右，遇到空结点时返回上一层向另一个孩子结点递归。
反序列化：首先将传来的字符串分割，将结点值保存在vector容器内，方便之后取值。接着按照前序遍历建树，取vector内权值新建结点。
3.具体代码
class Solution {
public:
char* Serialize(TreeNode *root) {
if(root==NULL)return "#";
string ans=to_string(root->val)+","+Serialize(root->left)+","+=Serialize(root->right);//字符数组可直接赋值到string
char* ans2=new char[ans.size()];
strcpy(ans2,ans.c_str());//字符串转字符数组
return ans2;
}
vector<string>v;//保存序列分割为各个结点的权值
void init(char* str){//从序列中划分出权值
string s;
for(int i=0;i<strlen(str);i++){//将序列分割
if(str[i]!=',')s+=str[i];
else{
v.push_back(s);
s.clear();
}
}
v.push_back(s);//最后一个权值后无','，要记得加上
size=v.size();
}
int cur=0,size;//当前结点编号，总的结点数
TreeNode* Deserialize(char *str) {
TreeNode* root=NULL;
if(!cur)init(str);//初始化，划分下字符串
if(cur<size&&v[cur]!="#"){//当前结点合法且不为NULL
root=new TreeNode(stoi(v[cur++]));//新建结点并递归左右
root->left=Deserialize(str);
root->right=Deserialize(str);
}else cur++;//NULL结点数目也要加加
return root;//返回当前子树根结点
}
};4.时间复杂度和空间复杂度分析
时间复杂度：，n是结点数，需要遍历二叉树所有结点
空间复杂度：，最坏情况下的递归树高度为n，每层一个结点。
方法二：层序遍历
1.解题思路
方法大致与上边类似，只是将DFS变为BFS，先序遍历变为层序遍历。
2.解法
- 序列化：层序遍历当前的二叉树，并用队列保存访问结点权值。在输出了字符串后发现后面拖了一串",#",是遍历最下边一层空结点时得到的，虽然与测试样例不同，但是不影响。
- 反序列化：首先将传来的字符串分割，将结点权值保存进vector容器内，方便之后取值。接着按照层序遍历建树，取vector内权值新建结点。注意当遍历到空结点时，也要令cur++，接着得到下一个结点权值用以新建结点。
3.图解
4.具体代码
class Solution {
public:
char* Serialize(TreeNode *root) {//序列化
if(root==NULL)return "#";
string ans;//保存最后的序列
queue<TreeNode*>q;//保存结点，用于层序遍历
q.push(root);//根结点入队
while(!q.empty()){//当队列非空时
TreeNode* t=q.front();//取队首元素并出队
q.pop();
if(t==NULL)ans+="#,";//当前指针指向为空结点，添加"#,"
else{
ans+=to_string(t->val)+",";//加上当前结点
q.push(t->left);//左右孩子入队
q.push(t->right);
}
}
for(int i=ans.size()-1;;i--){//也可以不写这段代码，我这里为了清除序列后多余的"#,"，显得序列好看
if(!isdigit(ans[i])){
ans.erase(i,1);
}else break;
}
char *s=new char[ans.size()+1];
strcpy(s,ans.c_str());//string转字符数组接着赋值给s
return s;
}
TreeNode* Deserialize(char *str) {//反序列化
if(str[0]=='#'||str=="")return NULL;
vector<string>v;//保存序列分割为各个结点权值
string s;
for(int i=0;i<strlen(str);i++){//将序列分割
if(str[i]!=',')s+=str[i];
else{
v.push_back(s);
s.clear();
}
}
v.push_back(s);//最后一个权值后无','，要记得加上
int cur=0,size=v.size();//当前结点编号，总的结点数
queue<TreeNode*>q;//层次遍历建立树
TreeNode* root=new TreeNode(stoi(v[cur++]));//初始化根结点
q.push(root);//根结点入队
while(!q.empty()){
TreeNode* t=q.front();//取队首元素并出队
q.pop();
if(cur<size&&v[cur]!="#"){//为出队结点构造他的左右孩子，并令其孩子也入队
t->left=new TreeNode(stoi(v[cur]));
q.push(t->left);
}
cur++;//结点数++
if(cur<size&&v[cur]!="#"){
t->right=new TreeNode(stoi(v[cur]));
q.push(t->right);
}
cur++;//结点数++
}
return root;//返回根结点
}
};5.时间复杂度和空间复杂度分析
时间复杂度：，n为树结点数，遍历过程中需要访问所有结点。
空间复杂度：，需要在队列中保存所有树结点。
京公网安备 11010502036488号