JZ37 序列化二叉树

题目难度：较难

题目描述：

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

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

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

例如，可以根据层序遍历的方案序列化，如下图:

层序序列化(即用函数Serialize转化)如上的二叉树转为"{1,2,3,#,#,6,7}"，再能够调用反序列化(Deserialize)将"{1,2,3,#,#,6,7}"构造成如上的二叉树。

当然你也可以根据满二叉树结点位置的标号规律来序列化，还可以根据先序遍历和中序遍历的结果来序列化。不对序列化之后的字符串进行约束，所以欢迎各种奇思妙想。

数据范围： 节点数 n≤100，树上每个节点的值满足 0≤val≤150 要求： 序列化和反序列化都是空间复杂度 O(n)，时间复杂度 O(n)

示例1:

输入：{1,2,3,#,#,6,7} 返回值：{1,2,3,#,#,6,7} 说明：如题面图

思路1:前序遍历

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
#include <cmath>
#include <cstring>
#include <string>
class Solution {
public:
  	void Serialize(TreeNode *root, string& str) {
      	if (!root) str += "#,";
      	else {
          	str += to_string(root->val) + ",";
          	Serialize(root->left, str);
          	Serialize(root->right, str);
        }
    }
  
  	char* Serialize(TreeNode *root) {
      	// 将char数组转换成string，方便调用库函数
      	string str;
      	Serialize(root, str);
      
      	// change char to string
      	char* res = new char[tmp.length()];
      	// strcpy() 会自动在字符串结尾加上‘\0’
      	strcpy(res, tmp.c_str());
      	return res;
    }
  
  	TreeNode* Deserialize(list<string>& dataArray) {
      	if (dataArray.front() == "#") {
          	dataArray.earse(dataArray.begin());
          	return nullptr;
        }
      	TreeNode* root = new TreeNode(stoi(dataArray.front()));
      	dataArray.earse(dataAray.begin());
      	root->left = Deserialize(dataArray);
      	root->right = Deserialize(dataArray);
      	return root;
    }
  
  	TreeNode* Deserialize(char *str) {
      	// change char to string
      	string data;
      	while (*str != '\0') {
          	data += *str;
          	str++;
        }
      
      	string str0;
      	list<string> dataArray;
      
      	for (auto & ch : data) {
          	if (ch == ',') {
              	dataArray.push_back(str0);
              	str0.clear();
            } else str.push_back(ch);
        }
      
      	if (!str0.empty()) {
          	dataArray.push_back(str0);
          str0.clear();
        }
      
      	return Deserialize(dataArray);
    }
}