297.二叉树的序列化与反序列化 (Hard)*

题目描述*

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

请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

示例*

你可以将以下二叉树：

序列化为 "[1,2,3,null,null,4,5]"

说明*

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

代码*

使用字符串流处理比较方便，标准库提供了 to_string 和 stoi 函数，不必自己编写。

/**
 * 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 "[]";
        }
        // 使用字符串流处理
        stringstream ss;
        queue<TreeNode*> helpQueue;
        helpQueue.push(root);
        TreeNode *cur = root;
        while(!helpQueue.empty()) {
            cur = helpQueue.front();
            helpQueue.pop();
            if(cur != nullptr) {
                helpQueue.push(cur->left);
                helpQueue.push(cur->right);
                ss << to_string(cur->val) << ",";
            }else {
                ss << "nullptr,";
            }
        }
        string res = ss.str();
        // 上面这样遍历会在末尾有一串多余的 nullptr
        res = delNullptr(res, "nullptr,");
        res = res.substr(0, res.size() - 1);
        return "[" + res + "]";
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        data = data.substr(1, data.length() - 2);
        if(data.length() == 0) {
            return nullptr;
        }
        string tmp;
        stringstream ss;
        ss.str(data);
        getline(ss, tmp, ',');
        TreeNode *root = new TreeNode(stoi(tmp));
        TreeNode *cur = root;
        queue<TreeNode*> helpQueue;
        helpQueue.push(root);
        while(true) {
            cur = helpQueue.front();
            helpQueue.pop();
            if(!getline(ss, tmp, ',')) {
                break;
            }
            if(tmp != "nullptr") {
                cur->left = new TreeNode(stoi(tmp));
                helpQueue.push(cur->left);
            }
            if(!getline(ss, tmp, ',')) {
                break;
            }
            if(tmp != "nullptr") {
                cur->right = new TreeNode(stoi(tmp));
                helpQueue.push(cur->right);
            }       
        }
        return root;
    }

    string delNullptr(string data, string target) {
        int len = target.length();
        // 去掉末尾的 target 字符串
        while(data.length() > len && data.substr(data.length() - len, len) == target) {
            data = data.substr(0, data.length() - len);
        }
        return data;
    }
};

最后更新: July 23, 2022