[剑指Offer] 61.序列化二叉树

题目描述

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

 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 {
13 public:
14     char* Serialize(TreeNode* root)
15     {
16         if (root == NULL)
17         {
18             return "#";
19         }
20         string cur_val = to_string(root->val);
21         cur_val += '!';
22         char* left = Serialize(root->left);
23         char* right = Serialize(root->right);
24         char* ret = new char[strlen(left) + strlen(right) + cur_val.size()];
25         strcpy(ret, cur_val.c_str());
26         strcat(ret, left);
27         strcat(ret, right);
28         return ret;
29     }
30     TreeNode* Deserialize(char* str)
31     {
32         return Decode(str);
33     }
34     TreeNode* Decode(char*& str)
35     {
36         if (*str == '#')
37         {
38             str ++;
39             return NULL;
40         }
41         string val;
42         while (*str != '!')
43         {
44             val += *str;
45             ++str;
46         }
47         TreeNode* new_node = new TreeNode(stoi(val));
48         ++str;
49         new_node->left = Decode(str);
50         new_node->right = Decode(str);
51 
52         return new_node;
53     }
54 };