BM39. [序列化二叉树]

https://www.nowcoder.com/exam/oj?tab=%E7%AE%97%E6%B3%95%E7%AF%87&topicId=295

BM39. 序列化二叉树

https://www.nowcoder.com/practice/cf7e25aa97c04cc1a68c8f040e71fb84?tpId=295&sfm=github&channel=nowcoder

序列化二叉树即找一种顺序存储二叉树的结点，并以相同的方式能够读取序列重新构建。
换种说法，就是遍历二叉树，记录每个结点，再以同样的方式遍历就可以还原二叉树。
遍历的方法有四种：先序遍历、中序遍历、后序遍历、层次遍历，理论上只要以相同的方式序列化或者反序列化，都可以解题。

方法一：先序遍历
具体做法：
创建两个功能函数用于递归。SerializeFunction函数负责先序递归，将结点转换为字符，因string类型更适合字符串相加，我采用先用string，再转换为char的策略。DeserializeFunction函数负责先序递归构建树，利用char的指针依次移动，识别结点的数值，加入树中。

class Solution {
public:
    //处理序列化的功能函数（递归）
    void SerializeFunction(TreeNode* root, string& str){
        if(root == NULL){// 如果指针为空，表示左子节点或右子节点为空，用#表示
            str += '#';
            return;
        }
        string temp = to_string(root->val); //根
        str += temp + '!';// 加!，区分结点 
        SerializeFunction(root->left, str); //左
        SerializeFunction(root->right, str);//右
    }
    char* Serialize(TreeNode *root) {    
        if(root == NULL) //处理空树
            return "#";
        string res;
        SerializeFunction(root, res);
        // 把str转换成char
        char* charRes = new char[res.length() + 1];
        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) {
        if(str == "#"){ //空序列对应空树
            return NULL;
        }
        TreeNode* res = DeserializeFunction(&str);
        return res;
    }
};

复杂度分析：

• 时间复杂度：O(n)，先序遍历，每个结点遍历一遍
• 空间复杂度：O(n)，递归栈最大深度