题目描述
序列化是指将一个数据结构转化为位序列的过程,因此可以将其存储在文件中或内存缓冲区中,以便稍后在相同或不同的计算机环境中恢复结构。
设计一个序列化和反序列化 N 叉树的算法。一个 N 叉树是指每个节点都有不超过 N 个孩子节点的有根树。序列化 / 反序列化算法的算法实现没有限制。你只需要保证 N 叉树可以被序列化为一个字符串并且该字符串可以被反序列化成原树结构即可。
样例
[1 [3[5 6] 2 4]]
算法1
一部分递归 , 一部分 栈
C++ 代码
class Codec {
public:
string encode(Node* root)
{
if(!root)
return "";
string res = to_string(root->val);
if(root->children.size() != 0)
{
string temp = "";
for(auto ele : root->children)
{
temp += encode(ele) + " ";
}
temp.pop_back();
string temp1 ="[" + temp + "]";
res = res + temp1;
}
return res ;
}
// Encodes a tree to a single string.
string serialize(Node* root) {
if(!root)
return "[]";
string name = "[" + encode(root) + "]";
// cout << name << endl;
return name;
}
// Decodes your encoded data to tree.
Node* deserialize(string data) {
if(data.compare(std::string{"[]"}) == 0)
return nullptr;
stack<Node*> tag;
Node* root = new Node(1);
tag.push(root);
Node* node = nullptr; // 记录,当遇到头结点时压入栈中
for(int i = 1; i < data.length(); i ++)
{
if(data[i] == '[')
{
tag.push(node);
}
else if(data[i] >= '0' && data[i] <= '9')
{
string val = "";
while(data[i] >= '0' && data[i] <= '9')
{
val += data[i];
i ++;
}
int value = std::stoi(val);
i --; // 还原,不然for循环时会出错
node = new Node(value);
tag.top()->children.push_back(node);
}
else if(data[i] == ' ')
{
continue;
}
else if(data[i] == ']')
{
tag.pop();
}
}
return root->children[0];
}
};
这道题需要会员哦, 为了做这道题,我竟然充了会员。。。。
leetcode的一个测试用例