C++算法：二叉树的序列化与反序列化

LeetCode297二叉树的序列化与反序列化

序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。
请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
提示: 输入输出格式与 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);
}
1
2
3
4
5
6
7
8
9
10
11
12

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 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 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;
}

};

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法，请下载《闻缺陷则喜算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境：

VS2022 C++17