LeetCode 二叉树的序列化与反序列化

序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。

请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

示例:

你可以将以下二叉树：
    1
   / \
  2   3
     / \
    4   5
序列化为 "[1,2,3,null,null,4,5]"


提示: 这与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。
说明: 不要使用类的成员 / 全局 / 静态变量来存储状态，你的序列化和反序列化算法应该是无状态的。

思路分析：不难发现题中给的示例序列化采取的层次遍历，所以我们序列化也采取层次遍历，反序列化也设计成逆层次遍历构造。（当然你也可以使用其他遍历方式）（因为题目要求不能使用类的成员/全局等变量，所以递归方法实现构造比较困难。）

关于层次遍历，请先翻阅我的博客 LeetCode 二叉树的层次遍历

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:
	//将二叉树序列化（采取层次遍历）
	string serialize(TreeNode* root) {
		string result = "[";
		queue<TreeNode*> myQue;//层次遍历辅助队列
		myQue.push(root);
		while (!myQue.empty()) {
			root = myQue.front();
			myQue.pop();
			if (root == NULL) {//特殊情况
				result += "null,";
				continue;
			}
			else {//这里不管左右子树是否为空，都需要入队列
				result += to_string(root->val) + ",";
                myQue.push(root->left);
			    myQue.push(root->right);
			}
		}
        
        //示例给出的序列化字符串为"[1,2,3,null,null,4,5]"
        //而按照上面的层次遍历得到的结果是"[1,2,3,null,null,4,5,null,null,null,null]"
        //因为当访问到最底层的节点时，左右子树不管都为空，任然会进入队列。
        
        //所以下面需要进行处理
		if (result == "[null,") {//如果这棵树为空，只需要去逗号
			result.resize(result.size() - 1);
		}
		else {//否则需要去掉多余的逗号、null
			int endIndex = result.size() - 1;
			//需要去掉末尾的逗号和多余的null
			while (result[endIndex] < '0' || result[endIndex] > '9') {
				endIndex -= 1;
			}
			result.resize(endIndex + 1);
		}
        result += "]";//最后别忘记了右括号
		return  result;
	}

	//反序列化
	TreeNode* deserialize(string data) {
        
        //首先将data字符串以逗号进行分割
		vector<string> dataVec;//data以逗号分隔开
		int dataSize = data.size();
		//取出中间的数据（null转换为INT_MIN
		for (int index = 1; index < dataSize - 1; ++index) {
			string tempData = "";
            //一直复制，直到遇到逗号
			while (index < dataSize - 1 && data[index] != ',') {
				tempData += data[index++];
			}
			dataVec.push_back(tempData);
		}
        
		//将层次遍历序列序列化为二叉树
		int dataVecSize = dataVec.size();
		queue<TreeNode*> myQue;//反序列化的辅助队列
		//层次遍历只为空节点的特殊情况
		if (dataVec[0] == "null") {
			return NULL;
		}
		TreeNode *result = new TreeNode(atoi(dataVec[0].c_str())), *tempPtr;//根节点，atoi(dataVec[0].c_str()转化为int
		myQue.push(result);
		for (int index = 1; index < dataVecSize; ++index) {
			tempPtr = myQue.front();//获取下一个即将构建的节点
			myQue.pop();
			//构建左子树
			if (dataVec[index] != "null") {
				tempPtr->left = new TreeNode(atoi(dataVec[index].c_str()));
				myQue.push(tempPtr->left);//记得要放入队列，因为左子树可能还需要构造
			}
			index += 1;//dataVec指针后移
			//构建右子树
			if (index < dataVecSize && dataVec[index] != "null") {
				tempPtr->right = new TreeNode(atoi(dataVec[index].c_str()));
				myQue.push(tempPtr->right);//记得要放入队列，因为右子树可能还需要构造
			}
		}
		return result;
	}
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));