作者:whisper
链接:https://www.proprogrammar.com/article/914
声明:请尊重原作者的劳动,如需转载请注明出处
请实现两个函数,分别用来序列化和反序列化二叉树。
示例:
你可以将以下二叉树:
1
/ \
2 3
/ \
4 5序列化为 "[1,2,3,null,null,4,5]"
难度:困难;标签:树,设计;编程语言:C++
/**
* 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 builder = "";
queue<TreeNode*> q;
TreeNode* temp;
int size;
if(root){
q.push(root);
while(!q.empty()){
size = q.size();
for(int i = 0; i < size; i++){
temp = q.front();
q.pop();
if(temp){
builder += to_string(temp->val) + " ";
q.push(temp->left);
q.push(temp->right);
}else{
builder += "NULL ";
}
}
}
}
return builder;
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
TreeNode* head = NULL, *temp, *n;
if(data != ""){
vector<string> split = split11(data, " ");
queue<TreeNode*> q;
head = new TreeNode(atoi(split[0].c_str()));
q.push(head);
int size, index = 0;
while(!q.empty()){
size = q.size();
for(int i = 0; i < size; i++){
temp = q.front();
q.pop();
index++;
if(split[index] != "NULL"){
n = new TreeNode(atoi(split[index].c_str()));
temp->left = n;
q.push(n);
}
index++;
if(split[index] != "NULL"){
n = new TreeNode(atoi(split[index].c_str()));
temp->right = n;
q.push(n);
}
}
}
}
return head;
}
vector<string> split11(const string& in, const string& delim)
{
vector<string> ret;
try
{
regex re{delim};
return vector<string>{
sregex_token_iterator(in.begin(), in.end(), re, -1),
sregex_token_iterator()
};
}
catch(const std::exception& e)
{
}
return ret;
}
};
// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));
split11方法为似java的string.split方法,按delim分割字符串为字符串数组,由题意二叉树是按层次序列化的,所以我们序列化时也按层次序列化,注意一个不是NULL的结点,他的NULL子结点也要序列化到结果中。反序列化时,也是按层次反序列化,两层一起操作,上一层反序列化,下一层做为子结点的同时入队列,上一层反序列化完成,Index指针到了下下一层,然后下一层,下下一层进行同样的操作,还是很有技巧性的,注意一下
/**
* 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:
int i;
bool getNum(string& data,int& num){
num = 0;
if(data[i]=='-'){
i++;
while(data[i]!=','&&data[i]!=']'){
num *= 10;
num += data[i]-'0';
i++;
}
num *= -1;
return true;
}
if(data[i]>='0'&&data[i]<='9'){
while(data[i]!=','&&data[i]!=']'){
num *= 10;
num += data[i]-'0';
i++;
}
return true;
}
else{
i = i+4;
return false;
}
}
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
if(!root)
return "[]";
string s;
s.push_back('[');
queue<TreeNode*> q;
q.push(root);
s += to_string(root->val);
s.push_back(',');
while(!q.empty()){
TreeNode* son = q.front();
q.pop();
if(son->left){
q.push(son->left);
s += to_string(son->left->val);
s.push_back(',');
}
else{
s += "null,";
}
if(son->right){
q.push(son->right);
s += to_string(son->right->val);
s.push_back(',');
}
else{
s += "null,";
}
}
s.pop_back();
s.push_back(']');
return s;
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
if(data.length()==2)
return NULL;
queue<TreeNode*> q;
cout << data<< endl;
int num = 0;
i=1;
getNum(data,num);
TreeNode* root=new TreeNode(num);
q.push(root);
TreeNode* cur;
while(!q.empty()){
cur = q.front();
q.pop();
i++;
if(getNum(data,num)){
TreeNode* leftson = new TreeNode(num);
cur->left = leftson;
q.push(leftson);
}
i++;
if(getNum(data,num)){
TreeNode* rightson = new TreeNode(num);
cur->right = rightson;
q.push(rightson);
}
}
return root;
}
};
// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));
做法基本一样,不同的是反序列化时我用的正则split11方法,这里是用的getNum方法来获取数字或者null
亲爱的读者:有时间可以点赞评论一下
月份 | 原创文章数 |
---|---|
202204 | 1 |
202203 | 11 |
202201 | 2 |
202108 | 7 |
202107 | 3 |
202106 | 16 |
202105 | 10 |
202104 | 16 |
202103 | 56 |
202102 | 14 |
202010 | 3 |
202009 | 3 |
202008 | 7 |
202007 | 7 |
202006 | 10 |
202005 | 11 |
202004 | 22 |
202003 | 52 |
202002 | 44 |
202001 | 83 |
201912 | 52 |
201911 | 29 |
201910 | 41 |
201909 | 99 |
201908 | 35 |
201907 | 73 |
201906 | 121 |
201811 | 1 |
201810 | 2 |
201804 | 1 |
201803 | 1 |
201802 | 1 |
201707 | 1 |
全部评论