# 二叉树的序列化与反序列化

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

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

<p><strong>提示: </strong>输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 <a href="/faq/#binary-tree">LeetCode 序列化二叉树的格式</a>。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。</p>

<p> </p>

<p><strong>示例 1：</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/09/15/serdeser.jpg" style="width: 442px; height: 324px;" />
<pre>
<strong>输入：</strong>root = [1,2,3,null,null,4,5]
<strong>输出：</strong>[1,2,3,null,null,4,5]
</pre>

<p><strong>示例 2：</strong></p>

<pre>
<strong>输入：</strong>root = []
<strong>输出：</strong>[]
</pre>

<p><strong>示例 3：</strong></p>

<pre>
<strong>输入：</strong>root = [1]
<strong>输出：</strong>[1]
</pre>

<p><strong>示例 4：</strong></p>

<pre>
<strong>输入：</strong>root = [1,2]
<strong>输出：</strong>[1,2]
</pre>

<p> </p>

<p><strong>提示：</strong></p>

<ul>
	<li>树中结点数在范围 <code>[0, 10<sup>4</sup>]</code> 内</li>
	<li><code>-1000 <= Node.val <= 1000</code></li>
</ul>

<p>以下错误的选项是？</p>

## aop

### before

```cpp
#include <bits/stdc++.h>
using namespace std;

struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
```
### after

```cpp

```

## 答案

```cpp
class Codec
{
public:
    string serialize(TreeNode *root)
    {
        if (!root)
            return "null ";
        return serialize(root->left) + serialize(root->right) + to_string(root->val);
    }

    TreeNode *helptrans(istringstream &ss)
    {
        string s;
        TreeNode *root = NULL;
        ss >> s;
        if (s == "null")
            return root;
        root = new TreeNode(stoi(s));
        root->right = helptrans(ss);
        root->left = helptrans(ss);
        return root;
    }

    TreeNode *deserialize(string data)
    {
        stringstream ss;
        ss << data;
        string s, trans;
        while (ss >> s)
            trans = s + " " + trans;
        istringstream st(trans);
        return helptrans(st);
    }
};
```

## 选项


### A

```cpp
class Codec
{
public:
    string serialize(TreeNode *root)
    {
        if (!root)
            return "#_";
        return to_string(root->val) + "_" + serialize(root->left) + serialize(root->right);
    }

    TreeNode *deserialize(string data)
    {
        cout << data << endl;
        queue<string> q;
        stringstream ss(data);
        string s;
        while (getline(ss, s, '_'))
            q.push(s);
        return help(q);
    }

    TreeNode *help(queue<string> &q)
    {
        auto cur = q.front();
        q.pop();
        if (cur == "#")
            return NULL;
        auto root = new TreeNode(stoi(cur));
        root->left = help(q);
        root->right = help(q);
        return root;
    }
};

```

### B

```cpp
class Codec
{
public:
    string serialize(TreeNode *root)
    {
        string ans;
        if (root == NULL)
            return "[]";
        ans = "[";
        queue<TreeNode *> que;
        que.push(root);

        char str[100];

        while (!que.empty())
        {
            TreeNode *top = que.front();
            que.pop();

            if (top != NULL)
            {
                que.push(top->left);
                que.push(top->right);

                sprintf(str, "%d", top->val);
                ans += str;
            }
            else
            {
                ans += "null";
            }

            ans += ",";
        }

        int end = ans.length() - 1;
        while (!(ans[end] >= '0' && ans[end] <= '9'))
            end--;

        string rs = ans.substr(0, end + 1);
        rs += "]";

        return rs;
    }

    TreeNode *deserialize(string data)
    {

        int len = data.size();

        if (len <= 2)
            return NULL;

        int numsCount = 0;
        vector<TreeNode *> nums;

        string word = "";
        for (int i = 1; i <= len - 2; i++)
        {
            if (data[i] == ',')
            {
                TreeNode *tmp = NULL;
                if (word == "null")
                {
                }
                else
                {
                    int num = atoi(word.c_str());
                    tmp = new TreeNode(num);
                }
                nums.push_back(tmp);
                word = "";
            }
            else
            {

                word += data[i];
            }
        }
        if (word != "" && word != "null")
        {
            int num = atoi(word.c_str());
            TreeNode *tmp = new TreeNode(num);
            nums.push_back(tmp);
        }

        int cnt = nums.size();

        int q = 0;
        int p = 1;
        while (p < cnt)
        {
            if (nums[q] == NULL)
            {
                q++;
            }
            else
            {
                if (p < cnt)
                    nums[q]->left = nums[p];
                if (p + 1 < cnt)
                    nums[q]->right = nums[p + 1];
                p += 2;
                q++;
            }
        }

        return nums[0];
    }
};
```

### C

```cpp
class Codec
{
public:
    string serialize(TreeNode *root)
    {
        string result = "[";
        queue<TreeNode *> myQue;
        myQue.push(root);
        while (!myQue.empty())
        {
            root = myQue.front();
            myQue.pop();
            if (root == NULL)
            {
                result += "null,";
                continue;
            }
            else
            {
                result += to_string(root->val) + ",";
                myQue.push(root->left);
                myQue.push(root->right);
            }
        }

        if (result == "[null,")
        {
            result.resize(result.size() - 1);
        }
        else
        {
            int endIndex = result.size() - 1;

            while (result[endIndex] < '0' || result[endIndex] > '9')
            {
                endIndex -= 1;
            }
            result.resize(endIndex + 1);
        }
        result += "]";
        return result;
    }

    TreeNode *deserialize(string data)
    {

        vector<string> dataVec;
        int dataSize = data.size();

        for (int index = 1; index < dataSize - 1; ++index)
        {
            string tempData = "";

            while (index < dataSize - 1 && data[index] != ',')
            {
                tempData += data[index++];
            }
            dataVec.push_back(tempData);
        }

        int dataVecSize = dataVec.size();
        queue<TreeNode *> myQue;

        if (dataVec[0] == "null")
        {
            return NULL;
        }
        TreeNode *result = new TreeNode(atoi(dataVec[0].c_str())), *tempPtr;
        myQue.push(result);
        for (int index = 1; index < dataVecSize; ++index)
        {
            tempPtr = myQue.front();
            myQue.pop();

            if (dataVec[index] != "null")
            {
                tempPtr->left = new TreeNode(atoi(dataVec[index].c_str()));
                myQue.push(tempPtr->left);
            }
            index += 1;

            if (index < dataVecSize && dataVec[index] != "null")
            {
                tempPtr->right = new TreeNode(atoi(dataVec[index].c_str()));
                myQue.push(tempPtr->right);
            }
        }
        return result;
    }
};
```
