449. 序列化和反序列化二叉搜索树
题意
- 给定一棵二叉搜索树,实现序列化和反序列化;
- 注意 val 范围,因此 在序列化时需要插入分隔符分割每个节点的 val;
- 要善于利用 二叉搜索树的特性(中序遍历 = 递增排序);
解法
- 前序遍历 + 中序遍历 可以重构一棵树,又由于二叉搜索树自带中序遍历,因此在序列化时保存前序遍历;
- 由于节点的
val
不一定是个位数,所以要在序列化时插入分隔符; - 在反序列化时,首先分割字符串,得到前序遍历,然后通过前序遍历和中序遍历进行二叉搜索树的重构。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Codec {
public:
void PreOrder(TreeNode* root, string& data)
{
if(root == nullptr) return;
data.append(to_string(root->val) + ","); // , 作为分隔符
// if(root->left != nullptr) 递归函数开头就判断了非空的情况,因此这里不需要再次判断了
PreOrder(root->left, data);
// if(root->right != nullptr) 递归函数开头就判断了非空的情况,因此这里不需要再次判断了
PreOrder(root->right, data);
}
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
string res = "";
PreOrder(root, res);
return res;
}
vector<int> Split(string data) // 将序列化后的 string 进行分割,得到每个节点的 val
{
int idx = 0;
int curS = 0;
vector<int> ans;
while(idx < data.size())
{
if(data[idx] == ',')
{
string cur = data.substr(curS, idx - curS);
ans.emplace_back(stoi(cur));
curS = idx + 1;
}
idx++;
}
return ans;
}
TreeNode* ReconstructTree(vector<int> data, int s, int t)
{
TreeNode* root = new TreeNode(data[s]);
int rightIdx = -1;
// 没有孩子
if(s == t)
return root;
// 寻找右孩子的根
for(int i = s + 1; i <= t; i++)
{
if(data[i] > root->val)
{
rightIdx = i;
break;
}
}
if(rightIdx == -1) // 没有右孩子
{
root->right = nullptr;
// 构建左孩子
root->left = ReconstructTree(data, s + 1, t);
}
else if(rightIdx == s + 1) // 没有左孩子
{
root->left = nullptr;
// 构建右孩子
root->right = ReconstructTree(data, s + 1, t);
}
else
{
// 有左孩子,构建左孩子和右孩子
root->left = ReconstructTree(data, s + 1, rightIdx - 1);
root->right = ReconstructTree(data, rightIdx, t);
}
return root;
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
if(data == "") return nullptr;
vector<int> intData = Split(data);
TreeNode* root = ReconstructTree(intData, 0, intData.size()-1);
return root;
}
};
// Your Codec object will be instantiated and called as such:
// Codec* ser = new Codec();
// Codec* deser = new Codec();
// string tree = ser->serialize(root);
// TreeNode* ans = deser->deserialize(tree);
// return ans;
复杂度
时间复杂度:O(N),序列化前序遍历每个节点,反序列化也是恢复每个节点;
空间复杂度:O(N),存储序列化后的字符串。文章来源地址https://www.toymoban.com/news/detail-694969.html
文章来源:https://www.toymoban.com/news/detail-694969.html
到了这里,关于【LeetCode - 每日一题】449. 序列化和反序列化二叉搜索树(23.09.04)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!