/
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
if(!root)return "NULL";
queue<TreeNode*>q;
q.push(root);
string k;k+='|';
while(!q.empty()){//层序遍历二叉树,并且以|作为分割符
TreeNode*pp=q.front();
q.pop();
if(pp)
k+=to_string(pp->val);
else{
k+="NULL";
}k+='|';
if(pp){//节点为NULL也要考虑进来,因为层序遍历想要唯一确定二叉树必备
q.push(pp->left);
q.push(pp->right);
}
}
return k;
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
if(data=="NULL"){return NULL;}
int index=0;
vector<int>m;
m.push_back(0);
while(index<data.size()){//把字符串里面的数字提取出来,NULL就设为特殊值-114514
if(data[index]=='|'&&index!=data.size()-1){
int index1=index;
int index2=0;
bool flag=false;
string j;
for(int i=index1+1;i<data.size();i++){
if(data[i]=='|'){
break;
}else if(data[i]=='N'){
flag=true;
break;
}else{
j+=data[i];
index2=i;
}
}
if(!flag){
m.push_back(stoi(j,0,10));
//index=index2+1;
}
else{
m.push_back(-114514);
//index+=5;
}
}
index++;
}
vector<TreeNode*>pi;
pi.push_back(NULL);
for(int i=1;i<m.size();i++){//初始化每一个节点
if(m[i]!=-114514){
TreeNode*root=new TreeNode(m[i]);
pi.push_back(root);
}else{
pi.push_back(NULL);
}
}
//cout<<pi.size()<<' '<<m.size()<<'\n';
queue<TreeNode*>dp;
dp.push(pi[1]);
int index3=1;
while(!dp.empty()){//根据层序遍历序列创建二叉树
TreeNode*rot=dp.front();
dp.pop();
index3+=1;
if(index3>=pi.size())break;//注意下标越界
if(pi[index3]){
rot->left=pi[index3];
dp.push(pi[index3]);
}
index3+=1;
if(index3>=pi.size())break;
if(pi[index3]){
rot->right=pi[index3];
dp.push(pi[index3]);
}
}
return pi[1];
}
};