剑指offer：序列化二叉树

题目描述：

请实现两个函数，分别用来序列化和反序列化二叉树

思路分析：

这里一开始有点不明白题目的意思。实际上序列化应该指把二叉树用某种编码方式表示，这里一般是字符串的形式。而反序列就是将之前生成的序列转化成二叉树。

常规的想法里面，编码二叉树无非就是前序、中序、后序或是层次，但是我们都直到前序遍历加上中序遍历才能确定一颗二叉树，所以需要引入一些额外的信息，对于空的指针有表示。

下面的代码当中，是利用了前序遍历来序列化二叉树，其中对于空指针用‘#'表示，且每个结点后会用','隔开。注意二叉树的值为整数，可能包含多位，因此转化为二叉树时，需要将字符串转化为整型。

代码：

 1 /*
 2 struct TreeNode {
 3     int val;
 4     struct TreeNode *left;
 5     struct TreeNode *right;
 6     TreeNode(int x) :
 7             val(x), left(NULL), right(NULL) {
 8     }
 9 };
10 */
11 class Solution {
12 public:
13     void SerializeCore(TreeNode* root, string &str)
14     {
15         if(!root)
16         {
17             str += '#';
18             return;
19         }
20         string tmp = to_string(root->val);
21         tmp += ',';
22         str += tmp;
23         SerializeCore(root->left, str);
24         SerializeCore(root->right, str);
25     }
26     char* Serialize(TreeNode *root) {    
27         if(!root)
28             return nullptr;
29         string str;
30         SerializeCore(root, str);
31         int len = str.length();
32         char* res = new char[len+1];
33         for(int i=0; i<str.length(); i++)
34         {
35             res[i] = str[i];
36         }
37         res[len] = '';
38         return res;
39         
40     }
41     TreeNode* DeserializeCore(char **str)
42     {
43         if(**str == '#')
44         {
45             (*str)++;
46             return nullptr;
47         }
48         
49         // 这里注意的是整数用了字符串做表示，一个字符仅表示一位，因此首先要进行转化
50         int num=0;
51         while(**str != ',' && **str != '')
52         {
53             num = num*10 + ((**str) - '0');
54             (*str)++;
55         }
56         TreeNode* root = new TreeNode(num);
57         if(**str == '')
58             return root;
59         else
60             (*str)++;
61         root->left = DeserializeCore(str);
62         root->right = DeserializeCore(str);
63         return root;
64     }
65     
66     TreeNode* Deserialize(char *str) {
67         if(!str)
68             return nullptr;
69         TreeNode* res = DeserializeCore(&str);
70         return res;
71     }
72 };