LeetCode-297: 二叉树的序列化与反序列化

一、题目描述

二、解题思路

这就是自己实现LeetCode输入输出二叉树的方法

对应给定的序列化二叉树字符串，需要知道这个字符串是二叉树层次遍历的结果
需要从字符串里得到各个节点元素值，将其保存到vector内，需要手动实现：
- split方法
- to_integer方法（考虑负数）
之后，按照完全二叉树进行二叉树的反序列化重建
- 这一过程需要保存上一层的节点，以免创建下一层时本层节点丢失，用一个队列保存
- 直到vector遍历完成
对二叉树进行序列化
- 本质就是层序遍历，遇到空节点，就插入"null"即可

三、解题代码

class Codec
{
   
public:
    // Encodes a tree to a single string.
    string serialize(TreeNode *root)
    {
   
        if (!root)
            return "";
        vector<TreeNode *> vec;
        string ret = "[";
        queue<TreeNode *> que;
        que.push(root);
        while (!que.empty())
        {
   
            auto tmp = que.front();
            que.pop();
            if (tmp)
            {
   
                que.push(tmp->left);
                que.push(tmp->right);
            }
            vec.push_back(tmp);
        }
        for (size_t i = 0; i < vec.size(); i++)
        {
   
            if (vec[i])
                ret += to_string(vec[i]->val) + ",";
            else
                ret += "null,";
        }
        ret[ret.size() - 1] = ']';
        return ret;
    }

    // Decodes your encoded data to tree.
    TreeNode *deserialize(string data)
    {
   
        if(!data.size())    return nullptr;
        vector<string> vec = split(data.substr(1, data.size() - 2));
        queue<TreeNode *> que;
        auto root = new TreeNode(to_integer(vec[0]));
        que.push(root);
        size_t cur_vec_loc = 1;
        for (cur_vec_loc = 1; cur_vec_loc < vec.size();)
        {
   
            queue<TreeNode *> tmp_que;
            while (!que.empty())
            {
   
                auto cur_root = que.front();
                que.pop();
                if (vec[cur_vec_loc] == "null")
                    cur_root->left = nullptr;
                else
                {
   
                    auto cur_left = new TreeNode(to_integer(vec[cur_vec_loc]));
                    cur_root->left = cur_left;
                    tmp_que.push(cur_left);
                }
                cur_vec_loc++;
                if (vec[cur_vec_loc] == "null")
                    cur_root->right = nullptr;
                else
                {
   
                    auto cur_right = new TreeNode(to_integer(vec[cur_vec_loc]));
                    cur_root->right = cur_right;
                    tmp_que.push(cur_right);
                }
                cur_vec_loc++;
            }
            que = tmp_que;
        }
        return root;
    }

private:
    vector<string> split(string oper)
    {
   
        size_t l = 0, r = 0;
        size_t len = oper.size();
        vector<string> ret;
        for (l = 0; l < len; l++)
        {
   
            for (r = l; r < len && oper[r] != ','; r++)
                ;
            auto cur_sln = oper.substr(l, r - l);
            l = r;
            ret.push_back(cur_sln);
        }
        return ret;
    }
    int to_integer(string str)
    {
   
        if(str[0] == '-')   return 0 - to_integer(str.substr(1, str.size() - 1));
        int sln = 0;
        for (size_t i = 0; i < str.size(); i++)
            sln = sln * 10 + str[i] - '0';
        return sln;
    }
};