序列化|质数筛

质数筛的思想与推广

其实就是一种预处理分组 避免重复计算与选择

lcr156

前序bfs把二叉树转成带null标记的字符串

再按层序规则把字符串还原成二叉树，还会删掉末尾多余的null标记

class Codec {
public:

// Encodes a tree to a single string.
string serialize(TreeNode* root)
{
if(root == nullptr) return "";

string res;
queue<TreeNode*> order;
order.push(root);

while (!order.empty())
{
int size = order.size();
while(size--)
{
auto top = order.front();
order.pop();

if(top == nullptr)
res+="null,";
else
{
res+=to_string(top->val)+",";
order.push(top->left);
order.push(top->right);
}
}
}
res.erase(res.size()-1);
while (res.size()>=5&&res.substr(res.size()-5,5)==",null")
res.erase(res.size()-5,5);
return res;
}

// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
TreeNode* head = new TreeNode();
if(data.size() == 0)
return nullptr;

vector<string> value;
int begin = 0 ,length = 0;
string value_part;
for(int i = 0;i<data.size();i++){
if(data[i] == ','){
value.push_back(data.substr(begin,length));
begin = i+1;
length = 0;
}
else
length++;
}
value.push_back(data.substr(begin,length));

head->val = stoi(value[0]);
queue<TreeNode*> tree;
tree.push(head);

int pos = 1;
while (pos<value.size()){
TreeNode *p = tree.front();
tree.pop();
if(value[pos]!="null") {
p->left = new TreeNode(stoi(value[pos]));
tree.push(p->left);
}
pos++;
if(pos<value.size()&&value[pos]!="null") {
p->right = new TreeNode(stoi(value[pos]));
tree.push(p->right);
}
pos++;
}
return head;
}
};