题目描述

请实现两个函数，分别用来序列化和反序列化二叉树

二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过某种符号表示空节点（#），以！表示一个结点值的结束（value!）。

二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。

例如，我们可以把一个只有根节点为1的二叉树序列化为”1,”，然后通过自己的函数来解析回这个二叉树。

解题思路

在序列化的过程中需注意以下几点：

遍历过程中遇到空结点，用'#'补充；
每个结点之间用','隔开；
以及在遍历完的序列最后添加，终止符'\0';

反序列化，即为序列化的逆过程。

代码

struct TreeNode
{
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
    TreeNode (int x): val(x), left(NULL), right(NULL) {}
};
class Solution
{
public:
    char* Serialize (TreeNode* root)
    {
        if (!root)
            return NULL;
        SerializeCore (root);
        
        int length = str.length();
        char* res = new char[length + 1];
        // 将字符串转换为字符（因为程序要求返回字符）
        for (int i = 0; i < length; i++)
        {
            res[i] = str[i];
        }
        res[length] = '\0'; // 添加终止符
        
        return res;
    }
    TreeNode*  Deserialize (char* str)
    {
        if (!str)
            return NULL;
        TreeNode* res = DeserializeCore (&str);
        return res;
    }
private:
    string str;
    // 通过前序遍历，得到输出的字符串
    void SerializeCore (TreeNode* root)
    {
        if (!root)
        {
            str += '#';
            return;
        }
        // 若不为空将，将当前结点转换为字符串
        string temp = to_string(root->val);
        str += temp;
        // 在每个结点之间添加 ','
        str += ',';
        
        SerializeCore (root->left);
        SerializeCore (root->right);
    }
    TreeNode* DeserializeCore (char** str)
    {
        if (**str == '#')
        {
            (*str)++;
            return NULL;
        }
        // 若不为空，则需要把第一个字符转化为整数
        int num = 0;
        while (**str != ',' && **str != '\0')
        {
            num = num * 10 + (**str - '0'); // 字符转换为整数
            (*str)++;
        }
        
        TreeNode* root = new TreeNode(num); // 把当前结点指向得出的值num
        if (**str == '\0')
            return root;
        else
            (*str)++;
        root->left = DeserializeCore (str);
        root->right = DeserializeCore (str);
        return root;
    }
};

参考博文链接：https://cuijiahua.com/blog/2018/01/basis_61.html