二叉树的序列化以及反序列化
请实现两个函数，分别用来序列化和反序列化二叉树，不对序列化之后的字符串进行约束，但要求能够根据序列化之后的字符串重新构造出一棵与原二叉树相同的树。
二叉树的序列化(Serialize)是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树等遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#）
二叉树的反序列化(Deserialize)是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。
链接：
代码示例
#include <string>
class Solution {
public:
void preOrder(TreeNode* root, string& str) {
if (!root) {
str += "#,";
return;
}
str += to_string(root->val) + ",";
preOrder(root->left, str);
preOrder(root->right, str);
}
char* Serialize(TreeNode* root) {
string ans;
preOrder(root, ans);
char* charAns = new char[ans.length() + 1];
strcpy(charAns, ans.c_str());
charAns[ans.length()] = '\0';
return charAns;
}
queue<string> getStrQ(char* s) {
queue<string> strQ;
string str;
char* p = s;
while (*p) {
if (*p != ',') {
str += *p;
} else {
strQ.push(str);
str.clear();
}
p++;
}
return strQ;
}
TreeNode* preOrderDes(queue<string>& strQ) {
if (strQ.front() == "#") {
strQ.pop();
return nullptr;
}
auto* root = new TreeNode(stoi(strQ.front()));
strQ.pop();
root->left = preOrderDes(strQ);
root->right = preOrderDes(strQ);
return root;
}
TreeNode* Deserialize(char* str) {
queue<string> strQ = getStrQ(str);
TreeNode* ans = preOrderDes(strQ);
return ans;
}
};
问题思考
waiting…
文档信息
- 本文作者：Chaojie Men
- 本文链接：https://menchaojie.github.io/2024/07/09/Serialize-Binary-Tree/
- 版权声明：自由转载-非商用-非衍生-保持署名（创意共享3.0许可证）