​LeetCode刷题实战297：二叉树的序列化与反序列化

智能摘要文章源自JAVA秀-https://www.javaxiu.com/33512.html

序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。请设计一个算法来实现二叉树的序列化与反序列化。反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。文章源自JAVA秀-https://www.javaxiu.com/33512.html

原文约 2751 字 | 图片 2 张 | 建议阅读 6 分钟 | 评价反馈文章源自JAVA秀-https://www.javaxiu.com/33512.html

​LeetCode刷题实战297：二叉树的序列化与反序列化

原创 小猿同学 程序IT圈 文章源自JAVA秀-https://www.javaxiu.com/33512.html

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选 ！文章源自JAVA秀-https://www.javaxiu.com/33512.html

文章源自JAVA秀-https://www.javaxiu.com/33512.html

今天和大家聊的问题叫做 二叉树的序列化与反序列化，我们先来看题面：文章源自JAVA秀-https://www.javaxiu.com/33512.html

https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/文章源自JAVA秀-https://www.javaxiu.com/33512.html

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.文章源自JAVA秀-https://www.javaxiu.com/33512.html

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.文章源自JAVA秀-https://www.javaxiu.com/33512.html

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.文章源自JAVA秀-https://www.javaxiu.com/33512.html

文章源自JAVA秀-https://www.javaxiu.com/33512.html

序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。文章源自JAVA秀-https://www.javaxiu.com/33512.html

请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。文章源自JAVA秀-https://www.javaxiu.com/33512.html

提示: 输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。文章源自JAVA秀-https://www.javaxiu.com/33512.html

文章源自JAVA秀-https://www.javaxiu.com/33512.html

示例

文章源自JAVA秀-https://www.javaxiu.com/33512.html

解题

文章源自JAVA秀-https://www.javaxiu.com/33512.html

序列化文章源自JAVA秀-https://www.javaxiu.com/33512.html

用一个string保存序列。文章源自JAVA秀-https://www.javaxiu.com/33512.html

使用先序遍历，遇到空结点，字符串保存‘#’。否则，当前节点的数字保存为字符串，用’!'号结尾。比如上面的例子，序列化后为“1!2!3!##4!5!”。文章源自JAVA秀-https://www.javaxiu.com/33512.html

文章源自JAVA秀-https://www.javaxiu.com/33512.html

反序列化文章源自JAVA秀-https://www.javaxiu.com/33512.html

遍历字符串，如果遇到‘#’，返回nullptr。否则根据’!'号，找到节点的数字字符串，转化为数字，创建新的节点。然后左右节点递归调用。文章源自JAVA秀-https://www.javaxiu.com/33512.html

/** * 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 == nullptr ) return "";        string ans = "";        serializeCore( root, ans );        return ans;    }    void serializeCore( TreeNode* node, string& seq ) {        if ( node == nullptr ) {            seq += '#';            return;        }        seq += to_string( node->val ) + '!';        serializeCore( node->left, seq );        serializeCore( node->right, seq );        return;    }    // Decodes your encoded data to tree.    TreeNode* deserialize(string data) {        if ( data == "" )            return nullptr;                    int index = 0;        return deserializeCore( data, index );    }    TreeNode* deserializeCore( string& str, int& index ) {        if ( str[index] == '#' ) {            ++index;            return nullptr;        }                int left = index;        while ( str[index] != '!' )            ++index;                string temp = str.substr( left, index - left );        TreeNode* node = new TreeNode( stoi( temp ) );        ++index;        node->left = deserializeCore( str, index );        node->right = deserializeCore( str, index );        return node;    }    int stoi( string& str ) {        int res = 0;        int sign = 1;        int i = 0;        if ( str[0] == '-' ) {            sign = -1;            i = 1;        }        while ( i < str.size() )            res = res * 10 + ( str[i++] - '0' );        return sign * res;    }};

好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力 。文章源自JAVA秀-https://www.javaxiu.com/33512.html

上期推文：文章源自JAVA秀-https://www.javaxiu.com/33512.html

LeetCode1-280题汇总，希望对你有点帮助！文章源自JAVA秀-https://www.javaxiu.com/33512.html

LeetCode刷题实战281：锯齿迭代器文章源自JAVA秀-https://www.javaxiu.com/33512.html

LeetCode刷题实战282：给表达式添加运算符文章源自JAVA秀-https://www.javaxiu.com/33512.html

LeetCode刷题实战283：移动零文章源自JAVA秀-https://www.javaxiu.com/33512.html

LeetCode刷题实战284：顶端迭代器文章源自JAVA秀-https://www.javaxiu.com/33512.html

LeetCode刷题实战285：二叉搜索树中的顺序后继文章源自JAVA秀-https://www.javaxiu.com/33512.html

LeetCode刷题实战286：墙和门文章源自JAVA秀-https://www.javaxiu.com/33512.html

LeetCode刷题实战287：寻找重复数文章源自JAVA秀-https://www.javaxiu.com/33512.html

LeetCode刷题实战288：单词的唯一缩写文章源自JAVA秀-https://www.javaxiu.com/33512.html

LeetCode刷题实战289：生命游戏文章源自JAVA秀-https://www.javaxiu.com/33512.html

LeetCode刷题实战290：单词规律文章源自JAVA秀-https://www.javaxiu.com/33512.html

LeetCode刷题实战291：单词规律II文章源自JAVA秀-https://www.javaxiu.com/33512.html

LeetCode刷题实战292：Nim 游戏文章源自JAVA秀-https://www.javaxiu.com/33512.html

LeetCode刷题实战293：翻转游戏文章源自JAVA秀-https://www.javaxiu.com/33512.html

LeetCode刷题实战294：翻转游戏II文章源自JAVA秀-https://www.javaxiu.com/33512.html

LeetCode刷题实战295：数据流的中位数文章源自JAVA秀-https://www.javaxiu.com/33512.html

LeetCode刷题实战296：最佳的碰头地点文章源自JAVA秀-https://www.javaxiu.com/33512.html

文章源自JAVA秀-https://www.javaxiu.com/33512.html