LCR 156. 序列化与反序列化二叉树

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

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

提示: 输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。
示例 1：

输入：root = [1,2,3,null,null,4,5]
输出：[1,2,3,null,null,4,5]

示例 2：
输入：root = []
输出：[]

示例 3：
输入：root = [1]
输出：[1]

示例 4：
输入：root = [1,2]
输出：[1,2]

提示：

• 树中结点数在范围 [0, 104] 内
• -1000 <= Node.val <= 1000

思路：
序列化：
1、按照层次遍历顺序收集每个节点的val，并追加到str；
2、遍历完毕之后，注意将str最后一个逗号删除。

反序列化：
1、将序列化的字符串以分隔符“，”进行切分，切分之后生成一个节点，存放在vector中；
2、以vector[0]为根节点，按照层次遍历的顺序，将节点插入以vector[0]为根节点的这棵树中。

/**
 * 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:

    // Encodes a tree to a single string.
string serialize(TreeNode* root) {
	//层次遍历
	string str = "";
	queue<TreeNode*> que;
	if (root==nullptr){
		return "null";
	}
	que.push(root);
	while (!que.empty()){
		TreeNode *node = que.front(); que.pop();
		
		if (node == nullptr){
			str += "null,";
		}
		else {
			str += to_string(node->val);
			str += ",";
			que.push(node->left);
			que.push(node->right);
		}
	}
	//str多了最后一个，
	str.pop_back();
    cout<<str<<endl;
	return str;
}

// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
	//数据切分
	vector<TreeNode*> vec;
	int len = data.length(),i=0;
	string str = "";
	while (i <= len-1){
		string tem = "";
		while(i<len && data[i] != ',') {
			tem += data[i++];
		}
        cout<<tem;
		if (tem == "null"){
			TreeNode* node = nullptr;
			vec.push_back(node);
		}
		else {
			TreeNode* node = new TreeNode(stoi(tem));
			vec.push_back(node);
		}
        i++;//移动到下一个位置
	}
	//以层次遍历的方式构造二叉树
	for (int i = 0,j = 1; j < vec.size(); i++){
		if (vec[i]==nullptr) continue;
		if (j < vec.size()) vec[i]->left = vec[j++];
		if (j < vec.size()) vec[i]->right = vec[j++];
	}
	return vec[0];//返回树的根
}
};

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