1.题目
请实现两个函数，分别用来序列化和反序列化二叉树
二叉树节点的定义:
struct TreeNode {
int val;
struct TreeNode *
left;
struct TreeNode *
right;
TreeNode(
int x) :
val(x),
left(
NULL),
right(
NULL) {
}
};
1.1 什么叫二叉树的序列化？
将二叉树变成一串字符序列。所谓的反序列二叉树即是从序列中重建出原始二叉树。
2.基本思路
序列化：
使用先序遍历，假设一个节点上存储的数值为1，则序列化为’1’。不同的节点之间使用,间隔。同时如果一个节点的子节点为NULL，则序列化为$
反序列化: 递归方法：
先重建一个节点重建节点的左子树重建节点的右子树
注意：在递归中，应该使字符序列变成全局变量，这样任何一个函数对字符串的修改，则能返回到主调函数中，从而继续用于左右子树的建立.
3.代码
char* Serialize(TreeNode *root) {
string res;
if(root==NULL)
return NULL;
stack<TreeNode*> s;
TreeNode *p=root;
char a[
100];
while(s.size() || p!=NULL )
{
if(p!=NULL)
{
sprintf(a,
"%d,",p->val);
res += a;
s.push(p);
p=p->left;
}
else{
res +=
"$,";
p=s.top();
s.pop();
p=p->right;
}
}
char *r=(
char *)res.c_str();
int _size=res.size();
r[_size-
1]=
'\0';
return r;
}
TreeNode* Decode(
char **
str)
{
if(**
str==
'\0')
return NULL;
if(**
str==
'$')
{
++(*
str);
if(**
str!=NULL)
++(*
str);
return NULL;
}
int num=
0;
while(**
str!=
',')
{
num = num*
10 +
int(**
str-
'0');
++(*
str);
}
++(*
str);
TreeNode *head=
new TreeNode(num);
head->left=Decode(
str);
head->right=Decode(
str);
return head;
}
TreeNode* Deserialize(
char *
str) {
if(
str==NULL)
return NULL;
if(*
str==
'\0')
return NULL;
return Decode(&
str);
}
