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

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

};