序列化二叉树

1、题目

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

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

二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。

例如，我们可以把一个只有根节点为1的二叉树序列化为"1,"，然后通过自己的函数来解析回这个二叉树

2、解题1

层次遍历的方法

/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } }; */ class Solution { public: char* Serialize(TreeNode *root) { if(root == NULL)return NULL; vector<char> result; queue<TreeNode*> que; que.push(root); while(que.size()>0){ char tmp; if(que.front() == NULL){ tmp = '#'; }else{ tmp = '0'+que.front()->val; que.push(que.front()->left); que.push(que.front()->right); } result.push_back(tmp); que.pop(); } char* str = (char*)malloc(sizeof(char)*(result.size()+1)); for(int i = 0;i<result.size();i++){ str[i] = result[i]; } str[result.size()] = '\0'; return str; } TreeNode* Deserialize(char *str) { if(str == NULL)return NULL; queue<TreeNode*>que1; queue<TreeNode*>que2; TreeNode* head = (TreeNode*)malloc(sizeof(TreeNode)); int val = (*str - '0'+256)%6; head->val = val; head->left = NULL; head->right = NULL; que1.push(head); str++; while(*str != '\0' && (!que1.empty() || !que2.empty())){ bool isLeft = true; while(!que1.empty()){ //节点 TreeNode* tmp = NULL; if(*str != '#'){ TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode)); int val = (*str - '0'+256)%6; node->val = val; node->left = NULL; node->right = NULL; tmp = node; que2.push(node); } //构建树 if(isLeft == true){ que1.front()->left = tmp; isLeft = false; }else{ que1.front()->right = tmp; isLeft = true; que1.pop(); } str++; } isLeft = true; while(!que2.empty()){ //节点 TreeNode* tmp = NULL; if(*str != '#'){ TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode)); int val = (*str - '0'+256)%6; node->val = val; node->left = NULL; node->right = NULL; tmp = node; que1.push(node); } //构建树 if(isLeft == true){ que2.front()->left = tmp; isLeft = false; }else{ que2.front()->right = tmp; isLeft = true; que2.pop(); } str++; } } return head; } };

3、解题2

前序遍历的方法

/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } }; */ class Solution { public: char* Serialize(TreeNode *root) { if(root == NULL)return NULL; vector<char> vec; SerializeHandle(root,vec); char* result = (char*)malloc(sizeof(char)*(vec.size()+1)); for(int i = 0;i<vec.size();i++){ result[i] = vec[i]; } result[vec.size()] = '\0'; return result; } //序列化 void SerializeHandle(TreeNode* root,vector<char> &vec){ if(root == NULL){ vec.push_back('#'); return; } char tmp = root->val+'0'; vec.push_back(tmp); SerializeHandle(root->left,vec); SerializeHandle(root->right,vec); } TreeNode* Deserialize(char *str) { if(str == NULL)return NULL; TreeNode* head = DeserializeHandle(str); return head; } //反序列化 TreeNode* DeserializeHandle(char*& str){ if(*str == '\0')return NULL; if(*str == '#'){ str++; return NULL; } TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode)); node->val = ((*str)-'0'+256)%6; str++; node->left = DeserializeHandle(str); node->right = DeserializeHandle(str); return node; } };