LeetCode刷题实战449：序列化和反序列化二叉搜索树-技术圈

LeetCode刷题实战449：序列化和反序列化二叉搜索树

共 3016字，需浏览 7分钟

· 2021-11-26

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从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;