最开始的思路是层序遍历，然后按照满二叉树记录每一层的所有节点，但是这样序列化造成的开销就太大了（一共要存 2^n-1 个节点），所以得另寻他法。
一般来说，恢复一棵二叉树是需要通过中序遍历+前序或后序中的一种，但这个方法有两个问题：一是如果两种序列在一个字符串中，就必须先将字符串全部扫描一遍才可以，不能边读取边建立；二是如果二叉树中节点数字出现重复，就没办法了。所以，这里不能使用这个办法。
其实，在前序遍历的时候不能确定一棵树的原因是它丢失了树上节点在哪里终止的信息，所以其实只要能将叶子节点（或只有一边有子树的节点）保留就能使用前序遍历来恢复二叉树。比如在遇到 NULL 的时候用一个特殊符号代替，这样在恢复的时候遇到 NULL 就开始回溯。
确定了思路以后就开始写代码，但是发现这道题比较麻烦的地方是涉及到的转换比较多。因为一开始并不知道节点的个数，所以在最开始不能确定 char*类型的长度，太长了浪费内存，太短了可能有的 case 跑不过。所以只能先用一个 vector 代替，最后返回之前将 vector 转换为 char*。另外，由于树的节点中存放的是 int，而返回的是 char*，所以如果 int 类型的数字未复数或大于 127 将无法使用 char 来表示，于是就只能将 int 转换成十进制字符串的形式来表示，到读取的时候还要将字符串在转换为 int。
最后，就是在遇到空的树的时候，转换程序可能会出问题，但是在接收函数中接受的类型是 char*，所以不能知道整个 char 的长度，于是有必须要有一个记录长度的地方，我就将 char*字符串内的第一位作为记录长度的区域，不过这里也有一个小坑，如果长度超过 127 ，程序就又挂了（然而测试用例没有超过的，就偷个懒不改了）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
|
class Solution {
public:
char* Serialize(TreeNode *root) {
vector<char> serial;
this->Seralize(root,&serial);
char* result=new char[serial.size()+1];
result[0]=serial.size();
for(int i=0;i<(int)(serial.size());i++){
result[i+1]=serial[i];
}
return result;
}
void Seralize(TreeNode* root,vector<char>* serial){
if(root==NULL) {
serial->push_back('*');
serial->push_back(',');
return;
}
this->Int2Char(root->val,serial);
this->Seralize(root->left,serial);
this->Seralize(root->right,serial);
}
void Int2Char(int val,vector<char>* serial){
if(val==0){
serial->push_back((char)48);
}else{
while(val>0){
serial->push_back((char)(val%10)+48);
val/=10;
}
}
serial->push_back(',');
}
TreeNode* Deserialize(char *str) {
int lenStr=sizeof(str)/sizeof(char);
if((int)(str[0])==2 && str[1]=='*') return NULL;
TreeNode* result;
int pos=1;
this->Deseralize(&result,str,&pos);
return result;
}
void Deseralize(TreeNode** root,char* str,int* pos){
if(str[*pos]!='*'){
*root=new TreeNode(this->Char2Int(str,pos));
this->Deseralize(&((*root)->left),str,pos);
this->Deseralize(&((*root)->right),str,pos);
}else{
(*pos)+=2;
}
}
int Char2Int(char* str,int* pos){
stack<int> s;
int val=0;
while(str[*pos]!=','){
s.push((int)(str[*pos]-48));
(*pos)++;
}
(*pos)++;
while(!s.empty()){
int t=s.top();
s.pop();
val*=10;
val+=t;
}
return val;
}
};
|