请实现两个函数，分别用来序列化和反序列化二叉树
二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#），以 ！ 表示一个结点值的结束（#!）或者(1!)。
二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。
例如，我们可以把一个只有根节点为1的二叉树序列化为"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) return "#!"; string res = to_string(root->val); res.push_back('!'); char *left = Serialize(root->left); char *right = Serialize(root->right); char *ret = new char[strlen(left) + strlen(right) + res.size()]; strcpy(ret, res.c_str());//注意这几个函数的使用 strcat(ret, left); strcat(ret, right); return ret; } TreeNode * deser(char *&s) { if(*s == '#') { s++; s++; return NULL; } int val = 0; while(*s != '!') { val = val*10 + (*s - '0'); s++; } s++; TreeNode *root = new TreeNode(val); root->left = deser(s); root->right = deser(s); return root; } TreeNode* Deserialize(char *str) { return deser(str); } };层次遍历：
/* 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) { string s; queue<TreeNode*> qt; qt.push(root); while (!qt.empty()) { // pop operator TreeNode *node = qt.front(); qt.pop(); // process null node if (node == nullptr) { s.push_back('#'); s.push_back('!'); continue; } // process not null node s += to_string(node->val); s.push_back('!'); // push operator qt.push(node->left); qt.push(node->right); } char *ret = new char[s.length() + 1]; strcpy(ret, s.c_str()); return ret; } TreeNode * Deserialize(char *str) { if (str == nullptr) { return nullptr; } // 可用string成员函数 string s(str); if (str[0] == '#') { return nullptr; } // 构造头结点 queue<TreeNode*> nodes; TreeNode *ret = new TreeNode(atoi(s.c_str())); s = s.substr(s.find_first_of('!') + 1); nodes.push(ret); // 根据序列化字符串再层次遍历一遍，来构造树 while (!nodes.empty() && !s.empty()) { TreeNode *node = nodes.front(); nodes.pop(); if (s[0] == '#') { node->left = nullptr; s = s.substr(2); } else { node->left = new TreeNode(atoi(s.c_str())); nodes.push(node->left); s = s.substr(s.find_first_of('!') + 1); } if (s[0] == '#') { node->right = nullptr; s = s.substr(2); } else { node->right = new TreeNode(atoi(s.c_str())); nodes.push(node->right); s = s.substr(s.find_first_of('!') + 1); } } return ret; } };