526互联

297. 二叉树的序列化与反序列化

发布时间 2023-05-16 22:24:27作者: WTSRUVF

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

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

提示: 输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。

 

示例 1：

输入：root = [1,2,3,null,null,4,5]
输出：[1,2,3,null,null,4,5]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

示例 4：

输入：root = [1,2]
输出：[1,2]

 

提示：

    树中结点数在范围 [0, 104] 内
    -1000 <= Node.val <= 1000


 

题解：

前序遍历序列化，然后前序遍历造树即可

vector加引用，不然会超时。。。。

/**
 * 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:

    void dfs(TreeNode* &root, vector<string> &vec)
    {
        if(root == NULL)
        {
            vec.push_back("null");
            return;
        }
        vec.push_back(to_string(root->val));
        dfs(root->left, vec);
        dfs(root->right, vec);
    }



    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        vector<string> vec;
        dfs(root, vec);
        string ret = "";

        for(int i = 0; i < vec.size(); i++)
        {
            if(i == 0)
                ret += vec[i];
            else
                ret += " " + vec[i];
        }

        return ret;
        
    }

    int to_int(string str)
    {
        int ret = 0, i = 0, flag = 0;
        if(str[0] == '-')
            flag = 1, i++;
        for(; i < str.size(); i++)
        {
            ret *= 10;
            ret += str[i] - '0';
        }
        return flag ? -ret : ret;
    }

    void build(TreeNode* &root, vector<string> &vec, int &k)
    {
        // if(k >= 300)
        //     cout << k << " ";
        if(k >= vec.size())
        {
            return;
        }
        if(vec[k] == "null")
        {
            root = NULL;
            k++;
            return;
        }
        root = (TreeNode *) malloc(sizeof(TreeNode));
        root->val = to_int(vec[k++]);
        build(root->left, vec, k);
        build(root->right, vec, k);
    }




    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        
        vector<string> vec;
        int j = 0;
        while(j < data.size())
        {
            string tmp = "";
            while(j < data.size() && data[j] != ' ') tmp += data[j++];
            vec.push_back(tmp);
            j++;
        }

        
        
        
        TreeNode* root = NULL;
        int k = 0;
        build(root, vec, k);



        return root;
        
    }
};

// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(root));