题解 | #序列化二叉树#

方法：递归

1、利用递归得到二叉树的前序遍历；

2、将前序遍历转换为二叉树。

代码中有很多细节需要处理：string和char类型之间的转换，字符与数字之间的转换。

时间复杂度：o(n)

空间复杂度：o(n)

class Solution {
  public:
    //前序遍历
    void SerializeFunction(TreeNode* root, string& str) {
        //空结点处理
        if (root == nullptr) {
            str += '#';
            return;
        }
        string temp = to_string(root->val);
        str += temp + '!'; //区分结点
        //左子树
        SerializeFunction(root->left, str);
        //右子树
        SerializeFunction(root->right, str);
    }
    char* Serialize(TreeNode* root) {
        string res;
        SerializeFunction(root, res);
        //string转换为char
        char* charRes = new char[res.length() + 1]; //最后一个以'\0'结尾
        strcpy(charRes, res.c_str());
        charRes[res.length()] = '\0';
        return charRes;
    }
    TreeNode* DeserializeFunction(char** str) {
        if (**str == '#') {
            (*str)++;
            return NULL;
        }
        //数字转换
        int val = 0;
        while (**str != '!' &&** str != '\0') {
            val = val * 10 + ((**str) - '0');
            (*str)++;
        }
        TreeNode* root = new TreeNode(val);
        //序列到底了，构建完成
        if (**str == '\0')
            return root;
        else
            (*str)++;
        //反序列化与序列化一致，都是前序
        root->left = DeserializeFunction(str);
        root->right = DeserializeFunction(str);
        return root;
    }
    TreeNode* Deserialize(char* str) {
        return DeserializeFunction(&str);
    }
};