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

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

## 扩展阅读

#### 视频课程

https://edu.csdn.net/course/detail/38771

https://edu.csdn.net/lecturer/6176

#### 相关下载

 鄙人想对大家说的话 闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 墨家名称的来源：有所得以墨记之。 如果程序是一条龙，那算法就是他的是睛

#### 测试环境

VS2022 C++17

|
29天前
|

【数据结构和算法】--- 二叉树（4）--二叉树链式结构的实现（2）
【数据结构和算法】--- 二叉树（4）--二叉树链式结构的实现（2）
17 0
|
13天前
|

【C++】二叉树进阶之二叉搜索树（下）
【C++】二叉树进阶之二叉搜索树（下）
15 4
|
13天前
|
Java 编译器 C++
【C++】二叉树进阶之二叉搜索树（上）
【C++】二叉树进阶之二叉搜索树（上）
14 3
|
20天前
|

17 3
|
20天前
|

【C++高阶】高效搜索的秘密：深入解析搜索二叉树
【C++高阶】高效搜索的秘密：深入解析搜索二叉树
23 2
|
22天前
|

C++ 补充之常用遍历算法
C++ 补充之常用遍历算法
17 1
|
29天前
|

18 1
|
29天前
|

【数据结构和算法】--- 二叉树（5）--二叉树OJ题
【数据结构和算法】--- 二叉树（5）--二叉树OJ题
16 1
|
19天前
|

JS 【详解】二叉树（含二叉树的前、中、后序遍历技巧和算法实现）
JS 【详解】二叉树（含二叉树的前、中、后序遍历技巧和算法实现）
20 0
|
29天前
|

C++之STL常用算法(遍历、查找、排序、拷贝、替换、算数生成、集合)
C++之STL常用算法(遍历、查找、排序、拷贝、替换、算数生成、集合)
19 0