#题目
序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。
请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
提示: 输入输出格式与 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, 10^4] 内
-1000 <= Node.val <= 1000
2023年6月版本
class Codec {
public:// Encodes a tree to a single string.
string serialize(TreeNode* root) {
auto str = serializeInner(root);
//std::cout << str << std::endl;
return str;
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
int iPos = 0;
return deserialize(data, iPos);
}private:
string serializeInner(TreeNode* root) {
if (nullptr == root)
{
return “()”;
}
return “(” + std::to_string(root->val) + serialize(root->left) + serialize(root->right) + “)”;
}
TreeNode* deserialize(string data,int& iPos)
{
if (iPos >= data.length())
{
return nullptr;
}
iPos++;
if ( ‘)’ == data[iPos])
{
iPos ++;
return nullptr;
}
int iValue = 0;
int iSign = 1;
if (‘-’ == data[iPos])
{
iSign = -1;
iPos++;
}
while (::isdigit(data[iPos]))
{
iValue = iValue * 10 + data[iPos] - ‘0’;
iPos++;
}
iValue = iSign;
TreeNode p = new TreeNode(iValue);
p->left = deserialize(data, iPos);
p->right = deserialize(data, iPos);
iPos++;
return p;
}
};2023年8月版
class Codec {
public:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
vector v;
std::queue<TreeNode*> que;
que.emplace(root);
while (que.size())
{
const auto cur = que.front();
que.pop();
if (nullptr == cur)
{
v.emplace_back(“”);
}
else
{
v.emplace_back(std::to_string(cur->val));
que.emplace(cur->left);
que.emplace(cur->right);
}
}
while (v.size() && (“” == v.back()))
{
v.pop_back();
}
string strRet;
for (const auto& s : v)
{
strRet += s + “,”;
}
return strRet;
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
vector v;
int left = 0;
for (int i = 0; i < data.size(); i++)
{
if (‘,’ == data[i])
{
v.emplace_back(data.substr(left, i - left));
left = i + 1;
}
}
if (0 == v.size())
{
return nullptr;
}
TreeNode* root = new TreeNode(atoi(v[0].c_str()));
std::queue<TreeNode*> que;
que.emplace(root);
int i = 1;
while ((i < v.size()) && que.size())
{
const auto cur = que.front();
que.pop();
if (“” != v[i])
{
cur->left = new TreeNode(atoi(v[i].c_str()));
que.emplace(cur->left);
}
i++;
if (i >= v.size())
{
break;
}
if (“” != v[i])
{
cur->right = new TreeNode(atoi(v[i].c_str()));
que.emplace(cur->right);
}
i++;
}
return root;
}};扩展阅读
相关下载
想高屋建瓴的学习算法，请下载《闻缺陷则喜算法册》doc版
鄙人想对大家说的话 |
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
墨家名称的来源：有所得以墨记之。 |
如果程序是一条龙，那算法就是他的是睛 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境：
VS2022 C++17
