LeetCode 297. Serialize and Deserialize Binary Tree
Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.
Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.
Clarification: The input/output format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.
Example 1:
Input: root = [1,2,3,null,null,4,5]
Output: [1,2,3,null,null,4,5]method
- 序列化
先序遍历，用#来表示空节点，用,作为节点之间的分隔
1 -> 1
/ \ / \
2 3 2 3
/ \ / \
# # # #序列化为1,2,#,#,3,#,#,
void dfs(TreeNode *root, string& res) {
if (!root) {
res += "#,";
return;
}
res += to_string(root->val) + ",";
dfs(root->left, res);
dfs(root->right, res);
return;
}
string serialize(TreeNode* root) {
string res = "";
if (!root) return res;
dfs(root, res);
return res;
}- 反序列化
- 将序列化中的节点值（包括
#）提取出来，去掉,，存储在队列中 - 也是用先序遍历，每次取队首作为根节点，然后出队，递归处理左右子树
因为要把序列第一个元素删掉，所以用队列比较方便，对队列的修改要用引用，不是回溯，所以同一层会不一样
// Decodes your encoded data to tree.
TreeNode* decode(queue<string>& data) { // 要用引用
if (data.front() == "#") {
data.pop();
return nullptr;
}
TreeNode *root = new TreeNode(stoi(data.front())); // string to int
data.pop();
root->left = decode(data); // 要用引用
root->right = decode(data); // 不然这两个q是一样的
return root;
}
TreeNode* deserialize(string data) {
if (data.size() == 0) return nullptr;
queue<string> q;
string s = "";
for (auto ch : data) {
if (ch == ',') {
q.push(s); // 存储节点值
s.clear();
}
else s.push_back(ch); // 几个字符合起来才是节点值，比如123
}
return decode(q);
}指针版本的，空节点就只有一个#，没有,了
class Solution {
public:
void dfs(TreeNode *root, string& data) {
if (!root) {
data += "#";
return;
}
data += to_string(root->val) + ",";
dfs(root->left, data);
dfs(root->right, data);
}
char* Serialize(TreeNode *root) {
if (!root) return "#";
string s = "";
dfs(root, s);
char *res = new char[s.length() + 1];
strcpy(res, s.c_str()); // s.c_str()返回的是const char*
return res;
}
TreeNode* decode(char *&s) { // 注意这里是指针的引用
if (*s == '#') {
++s;
return nullptr;
}
int num = 0;
while (*s != ',') {
num = num * 10 + (*s - '0');
++s;
}
++s;
TreeNode *root = new TreeNode(num);
root->left = decode(s);
root->right = decode(s);
return root;
}
TreeNode* Deserialize(char *str) {
printf("%s\n", str);
return decode(str);
}
};LeetCode 449. 序列化和反序列化二叉搜索树
序列化是将数据结构或对象转换为一系列位的过程，以便它可以存储在文件或内存缓冲区中，或通过网络连接链路传输，以便稍后在同一个或另一个计算机环境中重建。
设计一个算法来序列化和反序列化 二叉搜索树 。 对序列化/反序列化算法的工作方式没有限制。 您只需确保二叉搜索树可以序列化为字符串，并且可以将该字符串反序列化为最初的二叉搜索树。
编码的字符串应尽可能紧凑。
示例 1：
输入：root = [2,1,3]
输出：[2,1,3]method
可以使用『题297』的先序遍历方法，不过这样就没有用到BST的性质了
可以先用先序遍历得到字符串再转为数组，再用先序遍历构造BST
先序遍历构造二叉搜索树：根节点后面比它小的是左子树，比它大的是右子树
void dfs(TreeNode *root, string& res) {
if (!root) return;
res += to_string(root->val) + ",";
dfs(root->left, res);
dfs(root->right, res);
}
string serialize(TreeNode* root) {
string res;
if (!root) return res;
dfs(root, res);
return res;
}
TreeNode* decode(vector<int>& nums, int l, int r) {
if (l >= r) return nullptr; // [l, r)
TreeNode *node = new TreeNode(nums[l]);
int idx = l;
for (; idx < r; idx++) {
if (nums[idx] > nums[l]) break; // 找到第一个大于根节点的位置，后面就是右子树
}
node->left = decode(nums, l + 1, idx); // [l+1, idx)
node->right = decode(nums, idx, r); // [idx, r)
return node;
}
TreeNode* deserialize(string data) {
vector<int> nums;
int num = 0;
for (auto c : data) { // 将以,分割的字符串转为数组
if (c == ',') {
nums.push_back(num);
num = 0;
}
else num = num * 10 + c - '0';
}
return decode(nums, 0, nums.size());
}
