序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。
请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
示例：
你可以将以下二叉树：
1
/ 2 3
/ 4 5
序列化为 "[1,2,3,null,null,4,5]"
说明： 不要使用类的成员 / 全局 / 静态变量来存储状态，你的序列化和反序列化算法应该是无状态的。
题目链接： https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/
记录树的前序遍历序列（空节点也要记录，使用‘#‘表示），节点之间使用分隔符|进行分割。例如，示例中的树，其前序序列为1|2|#|#|3|4|#|#|5|#|#|，分割符的存在使得处理节点值是负数以及节点值是多位数字时更加方便。得到序列后，在反序列化时，首先将序列化的字符串按照分隔符|分开，然后根据序列使用先序创建二叉树的方法创建二叉树即可。代码如下：
/**
* 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) {
if(root==nullptr) return "";
string s = "";
serializeCore(root, s);
return s;
}
void serializeCore(TreeNode* root, string& s){
if(root==nullptr){
s += ‘#‘;
s += ‘|‘;
return;
}
s += to_string(root->val)+‘|‘;
serializeCore(root->left, s);
serializeCore(root->right, s);
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
if(data.empty()) return nullptr;
vector<string> tokens;
int start = 0;
for(int i=0; i<data.size(); i++){ // 将字符串序列分割成字符串vector
if(data[i]==‘|‘){
string temp = data.substr(start, i-start);
start = i+1;
tokens.push_back(temp);
}
}
int cur = 0;
TreeNode* root = deserializeCore(tokens, cur);
return root;
}
TreeNode* deserializeCore(vector<string> tokens, int& cur){
if(cur>=tokens.size()) return nullptr;
if(tokens[cur]=="#") return nullptr;
TreeNode* node = new TreeNode(atoi(tokens[cur].c_str()));
cur++;
node->left = deserializeCore(tokens, cur);
cur++;
node->right = deserializeCore(tokens, cur);
return node;
}
};
// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));
// 超时
该方法由于超时未通过，大概是因为分割字符串需要大量时间。
思路2的思想大致和思路1相同。思路1超时的原因是先对字符串进行分割，然后根据分割后的字符串数组建树，而分割字符串需要耗费大量时间。为了加快速度，可以边建树边分割字符串。我们使用两个指针left和right标记当前字符串的范围，用substr提取出当前字符后建树。代码如下（序列化代码和思路1一样，对反序列化代码进行了更改）：
/**
* 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) {
if(root==nullptr) return "";
string s = "";
serializeCore(root, s);
return s;
}
void serializeCore(TreeNode* root, string& s){
if(root==nullptr){
s += ‘#‘;
s += ‘|‘;
return;
}
s += to_string(root->val)+‘|‘;
serializeCore(root->left, s);
serializeCore(root->right, s);
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
if(data.empty()) return nullptr;
int left=0, right=0; // left, right标记当前字符的范围
TreeNode* root = deserializeCore(data, left, right);
return root;
}
TreeNode* deserializeCore(string data, int& left, int& right){
if(right>=data.length()) return nullptr;
while(right<data.length() && data[right]!=‘|‘) right++;
string curValStr = data.substr(left, right-left);
if(curValStr=="#") return nullptr;
TreeNode* node = new TreeNode(atoi(curValStr.c_str()));
left = right+1; right++;
node->left = deserializeCore(data, left, right);
left = right+1; right++;
node->right = deserializeCore(data, left, right);
return node;
}
};
// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));
原文：https://www.cnblogs.com/flix/p/12766160.html