Serialize and Deserialize Binary Tree

1，题目要求

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 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.

Clarification: The above 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.

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

序列化是将数据结构或对象转换为比特序列的过程，以便它可以存储在文件或存储缓冲器中，或者通过网络连接链路传输，以便稍后在相同或另一个计算机环境中重建。

设计一种算法来序列化和反序列化二叉树。序列化/反序列化算法的工作方式没有限制。您只需要确保二进制树可以序列化为字符串，并且可以将此字符串反序列化为原始树结构。

澄清：以上格式与LeetCode序列化二叉树的方式相同。您不一定需要遵循这种格式，因此请发挥创意并自己提出不同的方法。

注意：不要使用类成员/全局/静态变量来存储状态。您的序列化和反序列化算法应该是无状态的。

2，题目思路

对于这道题，要求将一颗二叉树序列化和反序列化。

所谓序列化 (Serialization)，是将对象的状态信息转换为可以存储或传输的形式的过程。

在这道题中，序列化是将一棵树转化为一个字符串，而反序列化是将字符串转化为一颗二叉树。

在实现序列化时，我们使用istringstream和ostringstream来实现串流风格的输入和输出。

istringstream类用于执行串流的输入操作。
ostringstream类用于执行串流的输出操作。

其中，空格作为字符串分隔符。

3，代码实现

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

static const auto s = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    return nullptr;
}();

class Codec {
public:

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

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        istringstream in(data);
        return deserializeHelper(in);
    }
private:
    void serializeHelper(TreeNode* root, ostringstream& out){
        if(root){
            out << root->val << ' ';
            serializeHelper(root->left, out);
            serializeHelper(root->right,out);
        }
        else{
            out << "# ";
        }
    }
    
    TreeNode* deserializeHelper(istringstream& in){
        string val;
        in >> val;
        if(val == "#")
            return nullptr;
        TreeNode* root = new TreeNode(stoi(val));
        root->left = deserializeHelper(in);
        root->right= deserializeHelper(in);
        return root;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));

Serialize and Deserialize Binary Tree

1，题目要求

2，题目思路

3，代码实现

相关推荐