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

来源:互联网
更新时间:2017/1/12 18:41:10
责任编辑:李志喜
字体:

 

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

 

参考资料:

https://discuss.leetcode.com/topic/72063/easy-bfs-java

 

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

www.xue163.com true http://www.xue163.com/3961/1/39619918.html report 9035 [LeetCode]SerializeandDeserializeBST二叉搜索树的序列化和去序列化,Serializationistheprocessofconvertingadatastructureorobjectintoasequenceofbitssothatitcanbestoredinafileormemorybuffer,ortran...
最近关注
首页推荐
热门图片
最新添加资讯
24小时热门资讯
精彩资讯
精彩推荐
热点推荐
真视界
精彩图片
社区精粹
关于本站 | 广告服务 | 手机版 | 商务合作 | 免责申明 | 招聘信息 | 联系我们
Copyright © 2004-2016 Xue163.com All Rights Reserved. 学网 版权所有
京ICP备10044368号-1 京公网安备11010802011102号
荐闻 | 学网头条知识问答 | 装修 | 作业 | 荐闻 | 学网头条精彩微信 | 新闻中心 | 软件教室 | 设计大全 | 网络相关 | 英语学习 | 开发编程 | 考试中心 | 参考范文 | 管理文库 | 营销中心 | 站长之家 | IT信息中心 | 商学院 | 数码大全 | 硬件DIY | 企业服务 | 网吧在线 | 问吧 | 百科 | 硬件知识 | 本网视点 | 文库 | 手机 | 平板 | 汽车 | 游戏 | 家电 | 精彩摄影 | 时尚科技 | 现代家居 | IT女人 | 经验 | 每日新闻 | 健康养生 | 图书馆 | 猎奇 | 精彩看点 | 图库 | 新闻中心 | 软件教室 | 设计大全 | 网络相关 | 英语学习 | 开发编程 | 考试中心 | 参考范文 | 管理文库 | 营销中心 | 站长之家 | IT信息中心 | 商学院 | 数码大全 | 硬件DIY | 企业服务 | 网吧在线 | 问吧 | 百科 | 硬件知识 | 本网视点 | 文库 | 手机 | 平板 | 汽车 | 游戏 | 家电 | 精彩摄影 | 时尚科技 | 现代家居 | IT女人 | 经验 | 每日新闻 | 健康养生 | 图书馆 | 精彩微信 | 猎奇 | 精彩看点 | 图库编程 方案 信息windows方案windows answer文档机构教育文档问答中心IT编程数码信息解决方案信息中心IT科技