题目描述
序列化二叉树
请实现两个函数,分别用来序列化和反序列化二叉树。
您需要确保二叉树可以序列化为字符串,并且可以将此字符串反序列化为原始树结构。
blablabla
样例
你可以序列化如下的二叉树
8
/ \
12 2
/ \
6 4
为:"[8, 12, 2, null, null, 6, 4, null, null, null, null]"
注意节点为负值的情况,下面代码里面有些。
C++ 代码
void dfs_s(TreeNode* root,string& res){
if(!root){
res=res+"null"+" ";
return;
}
res=res+to_string(root->val)+" ";
dfs_s(root->left,res);
dfs_s(root->right,res);
}
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
string res;
dfs_s(root,res);
return res;
}
TreeNode* dfs_d(string str,int &u){
if(u==str.size())return nullptr;
int k=u;
bool flag=false;
while(str[k]!=' ')k++;
if(str[u]=='n'){
u=k+1;
return nullptr;
}
int sum=0;
int i=0;
if(str[u]=='-'){
i=u+1;
flag=true;
}
else i=u;
for(;i<k;i++){
sum=sum*10+str[i]-'0';
}
u=k+1;
if(flag)sum=-sum;
auto root=new TreeNode(sum);
root->left=dfs_d(str,u);
root->right=dfs_d(str,u);
return root;
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
int u=0;
return dfs_d(data,u);
}