首页
登录 | 注册

[LeetCode] Serialize and Deserialize BST 二叉搜索树的序列化和去序列化

 

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 search tree. There is no restriction on how your serialization/deserialization algorithm should work. You just 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.

Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

 

这道题让我们对二叉搜索树序列化和去序列化,跟之前那道Serialize and Deserialize Binary Tree极其相似,虽然题目中说编码成的字符串要尽可能的紧凑,但是我们并没有发现跟之前那题有何不同,而且也没有看到能够利用BST性质的方法,姑且就按照之前题目的解法来写吧:

 

解法一:

class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
         ostringstream os;
         serialize(root, os);
         return os.str();
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        istringstream is(data);
        return deserialize(is);
    }
    
    void serialize(TreeNode* root, ostringstream& os) {
        if (!root) os << "# ";
        else {
            os << root->val << " ";
            serialize(root->left, os);
            serialize(root->right, os);
        }
    }
    
    TreeNode* deserialize(istringstream& is) {
        string val = "";
        is >> val;
        if (val == "#") return NULL;
        TreeNode* node = new TreeNode(stoi(val));
        node->left = deserialize(is);
        node->right = deserialize(is);
        return node;
    }
};

 

另一种方法是层序遍历的非递归解法,这种方法略微复杂一些,我们需要借助queue来做,本质是BFS算法,也不是很难理解,就是BFS算法的常规套路稍作修改即可,参见代码如下:

 

解法二:

class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if (!root) return "";
        ostringstream os;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            TreeNode *t = q.front(); q.pop();
            if (t) {
            os << t->val << " ";
            q.push(t->left);
            q.push(t->right);
            } else {
                os << "# ";
            }
        }
        return os.str();
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if (data.empty()) return NULL;
        istringstream is(data);
        queue<TreeNode*> q;
        string val = "";
        is >> val;
        TreeNode *res = new TreeNode(stoi(val)), *cur = res;
        q.push(cur);
        while (!q.empty()) {
            TreeNode *t = q.front(); q.pop();
            if (!(is >> val)) break;
            if (val != "#") {
                cur = new TreeNode(stoi(val));
                q.push(cur);
                t->left = cur;
            }
            if (!(is >> val)) break;
            if (val != "#") {
                cur = new TreeNode(stoi(val));
                q.push(cur);
                t->right = cur;
            }
        }
        return res;
    }
};

 

类似题目:

Serialize and Deserialize Binary Tree

Find Duplicate Subtrees

Serialize and Deserialize N-ary Tree

 

参考资料:

https://leetcode.com/problems/serialize-and-deserialize-bst

https://leetcode.com/problems/serialize-and-deserialize-bst/discuss/93260/easy-bfs-java

 

LeetCode All in One 题目讲解汇总(持续更新中...)


相关文章

  • Spring入门(二):自动化装配bean
    Spring从两个角度来实现自动化装配: 组件扫描(component scanning):Spring会自动发现应用上下文中需要创建的bean. 自动装配(autowiring):Spring会自动满足bean之间的依赖. 为了更形象的解 ...
  • 使用 ASP.NET Core MVC 创建 Web API(二)
    使用 ASP.NET Core MVC 创建 Web API 使用 ASP.NET Core MVC 创建 Web API(一)     六.添加数据库上下文       数据库上下文是使用Entity Framework Core功能的主 ...
  • 前言:最近一直在刷leetcode的题,用到isalnum函数,用man手册查找了一下,总共有13个相关函数如下: #include <ctype.h> int isalnum(int c); int isalpha(int c ...
  • 前言:取得成功的要自律!可能有一腔热血,努力很长一阵子,但过一阵子之后,就不坚持了,所以要自律去约束自己时刻坚持着! 一.收获 8月份的收获还是很大的,主要有以下几个方面: 学会了使用github 注册账号很长时间了,但不怎么会用,这个月, ...
  • 补习系列(20)-大话 WebSocket 与 &quot;尬聊&quot;的实现
    目录 一.聊聊 WebSocket 二.Stomp 是个什么鬼 三.SpringBoot 整合 WebSocket A. 引入依赖 B. WebSocket 配置 C. 控制器 D. 前端实现 四.参考文档 一.聊聊 WebSocket 从 ...
  • 页面性能优化-原生JS实现图片懒加载
         在项目开发中,我们往往会遇到一个页面需要加载很多图片的情况.我们可以一次性加载全部的图片,但是考虑到用户有可能只浏览部分图片.所以我们需要对图片加载进行优化,只加载浏览器窗口内的图片,当用户滚动时,再加载更多的图片.这种加载图片的 ...

2019 cecdns.com webmaster#cecdns.com
12 q. 0.079 s.
京ICP备10005923号