LeetCode刷题实战449:序列化和反序列化二叉搜索树
算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !
今天和大家聊的问题叫做 序列化和反序列化二叉搜索树,我们先来看题面:
https://leetcode-cn.com/problems/serialize-and-deserialize-bst/
Serialization is 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 search tree. There is no restriction on how your serialization/deserialization algorithm should work. You need to ensure that a binary search tree can be serialized to a string, and this string can be deserialized to the original tree structure. The encoded string should be as compact as possible.
序列化是将数据结构或对象转换为一系列位的过程,以便它可以存储在文件或内存缓冲区中,或通过网络连接链路传输,以便稍后在同一个或另一个计算机环境中重建。
设计一个算法来序列化和反序列化 二叉搜索树 。对序列化/反序列化算法的工作方式没有限制。您只需确保二叉搜索树可以序列化为字符串,并且可以将该字符串反序列化为最初的二叉搜索树。
编码的字符串应尽可能紧凑。
示例
示例 1:
输入:root = [2,1,3]
输出:[2,1,3]
示例 2:
输入:root = []
输出:[]
解题
https://zhuanlan.zhihu.com/p/269128835
主要思路:
要进行序列化和反序列化,我们需要把树用一个字符串来表示,并且能够根据这个字符串唯一地确定二叉搜索树的形态。由于二叉搜索树本身存在“中序遍历得到的序列是递增序列”这样的性质,我们就要解决如何解决空节点的表示的问题 这里我们把空节点用"#"来表示,遍历一遍二叉搜索树,把树转化成一个字符串表示起来,这是序列化的过程。反序列化的时候,再根据序列化得到的字符串恢复二叉搜索树。
这里有个技巧,序列化的时候,字符串是根节点的值 + 一个空格 + 左子树序列化后的字符串 + 一个空格 + 右子树序列化后的字符串。
因此在反序列化的时候,可以使用stringstream自动对空格进行分割,然后最开始得到的字串就是根节点的值,第二段字串是左子树,第三段字串是右子树。在对左、右子树进行恢复(反序列化)的时候,可以递归的调用decode()方法。
/**
* 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:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
if(root == NULL) { // 空节点用"#"表示
return "#";
}
return to_string(root -> val) + ' ' + serialize(root -> left) + ' ' + serialize(root -> right);
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
stringstream ss(data);
return decode(ss);
}
TreeNode* decode(stringstream &ss) {
string data;
ss >> data;
if(data == "#") {
return NULL;
}
TreeNode* root = new TreeNode(stoi(data)); // stringstream读到的第一段字符串是根节点的值
root -> left = decode(ss); // 递归调用decode()方法对左右子树建树,并将root与左右子树连接起来
root -> right = decode(ss);
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;
好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力 。
上期推文:
相关文章
- 快速学会SVN的搭建和使用
- C++程序设计:原理与实践(进阶篇)15.6 实例:一个简单的文本编辑器
- C++程序设计:原理与实践(进阶篇)15.8 调整vector类达到STL版本的功能
- 15.9 调整内置数组达到STL版本的功能
- C++程序设计:原理与实践(进阶篇)15.9 调整内置数组达到STL版本的功能
- C++程序设计:原理与实践(进阶篇)15.10 容器概览
- C++程序设计:原理与实践(进阶篇)16.1 标准库算法
- C++程序设计:原理与实践(进阶篇)16.2 最简单的算法f?ind()
- C++程序设计:原理与实践(进阶篇)16.3 通用搜索算法f?ind_if()
- C++程序设计:原理与实践(进阶篇)16.4 函数对象
- C++程序设计:原理与实践(进阶篇)15.1 存储和处理数据
- JAVA-String 中删除指定字符(11种方法)
- 为自定义对象生成随机属性值
- 利用Fork/Join框架来统计某个字符串在某个文件夹的文件中出现的次数
- 创建一个简单的web服务器
- 集合和Collections、Map的UML类图
- 多线程之线程池newFixedThreadPool(二)
- 多线程之volatile关键字
- 解决RocketMQ报No route info of this topic:异常
- Linux环境下安装RocketMQ(MetaQ)