序列化二叉树

知识点：二叉树递归

**递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。因此递归过程，最重要的就是查看能不能讲原本的问题分解为更小的子问题，这是使用递归的关键。**而二叉树的递归，则是将某个节点的左子树、右子树看成一颗完整的树，那么对于子树的访问或者操作就是对于原树的访问或者操作的子问题，因此可以自我调用函数不断进入子树。

思路：（递归）

序列化即将二叉树的节点值取出，放入一个字符串中，我们可以按照前序遍历的思路，遍历二叉树每个节点，并将节点值存储在字符串中，我们用‘#’表示空节点，用‘!'表示节点与节点之间的分割。

反序列化即根据给定的字符串，将二叉树重建，因为字符串中的顺序是前序遍历，因此我们重建的时候也是前序遍历，即可还原。

代码：

#include <cstddef>
class Solution {
public:
    void SerializeFunction(TreeNode* root,string& str){
        //如果是空树，就直接在字符串中加入字符“#”,就可以结束
        if(root==NULL){
            str+='#';
            return;
        }
        //否则就将根节点的值转化为字符串to_string()函数
        //再将这个根节点的字符后面加一个间隔节点的标识符'!'
        //之后通过递归将左子树和右子树都进行序列化
        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 str;
        SerializeFunction(root,str);
        //由于最后是需要返回的是字符数组的首地址
        //所以可以创建一个字符指针new一个新的字符数组，
        //再调用strcpy函数将字符串转化为字符，不要忘记字符串需要先转化为c_str()
        //在字符数组的最后加一个结束的标志符'\0'
        char* now=new char[str.length()+1];
        strcpy(now,str.c_str());
        now[str.length()]='\0';
        return now;
    }
    //注意对于反序列函数，传入的是指向字符串的首地址的指针，又开设了一个指针指向存了字符串的首地址的指针
     //所以*str表示地址，**str表示具体的字符
    TreeNode* Deserialize(char** str){
        //如果是空树，就返回null
        if(**str=='#'){
            (*str)++;
            return NULL;
        }
        //否则就根据间隔符！和结束符\0，将每个节点的值求出来，即将字符转化为数字
        //创建对应的节点
        //进行判断一下如果这棵树只有一个根节点，就直接返回根节点即可
        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=Deserialize(str);
        root->right=Deserialize(str);
        return root;

    }
    //进行反序列化，转化为二叉树
    TreeNode* Deserialize(char *str) {
        //如果字符串时“#”,则表示是空树，就直接返回null
        if(str=="#"){
            return NULL;
        }
        //否则就传入str，调用反序列的函数，注意传入的是字符串的首地址
        TreeNode* res=Deserialize(&str);
        return res;
    }
};