BM39 序列化二叉树

请实现两个函数，分别用来序列化和反序列化二叉树，不对序列化之后的字符串进行约束，但要求能够根据序列化之后的字符串重新构造出一棵与原二叉树相同的树。

二叉树的序列化(Serialize)是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。

序列化可以基于先序、中序、后序、层序的二叉树等遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#）
二叉树的反序列化(Deserialize)是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。

struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
		val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
	char* Serialize(TreeNode *root) {
		if (root == nullptr)
			return nullptr;
		queue q;
		q.push(root);
		string res = to_string(root->val) + '!';//用！分割字符,int转string函数to_string()
		while (!q.empty())
		{
			for (int i = 0; i < q.size(); ++i)
			{
				TreeNode* node = q.front();
				q.pop();

				if (node->left == nullptr)
					res += "#";
				else
				{
					res += to_string(node->left->val) + '!';
					q.push(node->left);
				}
					

				if (node->right == nullptr)
					res += "#";
				else
				{
					res += to_string(node->right->val) + '!';
					q.push(node->right);
				}					

			}
		}
		//char* ans = (char*)res.c_str();//将const char*强制转换成char*的类型
		char* ans = new char[res.size() + 1];//char数组以\0结尾，所以需要多加1位，‘\0’是一个字符
		strcpy(ans, res.c_str());//将res赋值给ans
		return ans;

	}
	TreeNode* Deserialize(char *str) {
		if (!str)
			return nullptr;

		string res = str;//转换成string
		int p = 0;//字符串指针
		int val = 0;
		while (str[p] != '!'&&p < res.length())
		{
			val = val * 10 + (str[p++] - '0');//根节点的val
		}
		p++;
		TreeNode* root=new TreeNode(val);
		queue q;
		q.push(root);

		while( p < res.length())
		{
			TreeNode* node = q.front();
			q.pop();
			TreeNode* left = nullptr, *right = nullptr;

			if (p < res.length()&&str[p] != '#')
			{
				val = 0;
				while (str[p] != '!'&&p < res.length())
				{
					val = val * 10 + (str[p++] - '0');
				}
				left=new TreeNode(val);
				q.push(left);
			}
			node->left = left;
			++p;
			if (p < res.length() && str[p] != '#')
			{
				val = 0;
				while (str[p] != '!'&&p < res.length())
				{
					val = val * 10 + (str[p++] - '0');
				}
				right = new TreeNode(val);
				q.push(right);
			}
			node->right = right;
			++p;
		}
		return root;
	}
};