剑指offer61：序列化二叉树

1 题目描述

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

　　二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过某种符号表示空节点（#），以！表示一个结点值的结束（value!）。
　　二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。

2 思路和方法

　　思路1：将问题分解为左子树、根节点、右子树分别进行递归处理。序列化是从根开始的，那么对应的反序列化在根节点的先序遍历中就可以得到。用’#'表示遍历过程中的nullptr，通过先序遍历得到序列。如：0,1,3,###2,4,##5,##。反序列化：如上式，首先得到数字0，作为根节点；然后得到数字1，是根节点的左子节点，接着得到3，是1的左子节点；接着得到两个’#‘,说明3为叶子结点，左右孩子都是空。然后得到’#’,说明1的右子节点为空；接着得到2，说明0的右子节点为2；以此类推。

　　思路2：先序存储记录，vector转化为整型后在（）char*）：int *res=new int[bufSize];　　 for(int i=0;i<bufSize;i++)　　 res[i]=buf[i]; 　　return (char*)res;　　反序列化，字符串转化为int， int *p=(int*)str; return dfs2(p); TreeNode* res=new TreeNode(*p); p++; res->left=dfs2(p); res->right=dfs2(p);

3 C++核心代码

 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     char* Serialize(TreeNode *root) {
14 
15         if(root == nullptr){
16             return "#";
17         }
18 
19         string s = to_string(root->val);
20         s.push_back(',');
21         char *left = Serialize(root->left);
22         char *right = Serialize(root->right);
23         char *ret = new char[strlen(left) + strlen(right) + s.size()];
24         strcpy(ret,s.c_str());
25         strcat(ret,left);
26         strcat(ret,right);
27         return ret;
28     }
29     // 注意参数类型应该为char *&str
30     TreeNode* Deserialize(char *&str) {
31         if (*str == '#'){
32             str ++;
33             return nullptr;
34         }
35         int num = 0;
36         while (*str!=','){
37             num = num * 10 + (*(str++) - '0');
38         }
39         str ++; // 跳过','
40         TreeNode *root = new TreeNode(num);
41         root->left = Deserialize(str);
42         root->right = Deserialize(str);
43         return root;
44     }
45 };

View Code

 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     vector<int> buf;
14     void dfs1(TreeNode *root) {
15         if(!root) buf.push_back(0xFFFFFFFF);
16         else {
17             buf.push_back(root->val);
18             dfs1(root->left);
19             dfs1(root->right);
20         }
21     }
22     TreeNode* dfs2(int* &p) {
23         if(*p==0xFFFFFFFF) {
24             p++;
25             return NULL;
26         }
27         TreeNode* res=new TreeNode(*p);
28         p++;
29         res->left=dfs2(p);
30         res->right=dfs2(p);
31         return res;
32     }
33     char* Serialize(TreeNode *root) {
34         buf.clear();
35         dfs1(root);
36         int bufSize=buf.size();
37         int *res=new int[bufSize];
38         for(int i=0;i<bufSize;i++) res[i]=buf[i];
39         return (char*)res;
40     }
41     TreeNode* Deserialize(char *str) {
42         int *p=(int*)str;
43         return dfs2(p);
44     }
45 };

View Code

参考资料

https://blog.csdn.net/zjwreal/article/details/89288722

https://blog.csdn.net/u012477435/article/details/83351659#_1782