38. 序列化和反序列化二叉树

题目：
直白些翻译就是把一个二叉树转换成一个字符串（序列化），同时你又可以根据这个字符串把这棵二叉树还原回来（反序列化）

思路：

• 一种比较复杂的思路是结合重建二叉树的题目，找到前序遍历、中序遍历，然后使用重建二叉树的方法实现反序列化，这样序列化则比较容易了，就是前序遍历和中序遍历。整体操作和设计较复杂
• 一种比较思路清晰的方式是只用二叉树的一种遍历方式，比如前序遍历，但是把空指针也表示出来，这样只需要遍历一次就可以实现序列化，同时因为表示了空指针，也能达到反序列化的效果

难点：
序列化过程：

• string中需要用到哪些方法？
  • int变str，用来保存树节点的数据，to_string(int val)
  • 拼接操作，用来把各个节点拼接起来，以及添加分隔符 string str1+char char2 或者 string str1 + string str2

反序列化过程：

• string中需要用到哪些方法？
  • 题目中用的char *
• 字符串中的数字如何变成整型？
  • num*10+char-‘0’
• 注意反序列化的过程中到达结尾处'\0'的处理，遇到'\0'要返回当前构造的node。
• 注意值有可能是负数，所以还需要设置一个bool标志变量

指针型的引用变量：

• char *&p 代表传入函数的是同一个指针p
• char &*p 没有这种写法
• 拓展说一说const, const char * p,char const * p两种写法是等价的，代表p指针指向的是一个常量，不能通过p去修改p的值，但可以改变p的指向，编译器会认为p指向谁，谁就是常量；char * const p,p指针本身是常量，不能修改p指针的指向，但可以修改p的值

代码：
100%正确的代码

class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string str;
        if(root==nullptr)
            return str;//不要返回NULL或nullptr，否则反序列化会出错，
//因为cpp中无法判断string对象是否为null值
        
        serialize(root,str);
        return str;
    }
    
    void serialize(TreeNode *root,string &str){
        if(root==nullptr){
            str+='#';
            return ;
        }
        str+=to_string(root->val);
        str+=',';
        serialize(root->left,str);
        serialize(root->right,str);
        
         
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if(data.empty())
            return nullptr;
        int n=0;
        return deserialize(data,n);
    }
    //使用&str可以节省大量内存空间，也会提高程序运行效率
    TreeNode *deserialize(string &str,int &index){
        if(str.empty())
            return nullptr;
        if(str[index]=='#')
            {
            index++;
            return nullptr;}
        int num=0;
        bool flag=false;
        if(str[index]=='-'){
            flag=true;
            index++;
        }
        while(str[index]!=',' && index<str.size()){
            num*=10;
            num+=str[index]-'0';
            index++;
        }
        if(flag)
            num*=-1;
        TreeNode *node=new TreeNode(num);
        if(index==str.size())
            return node;
        else
            index++;
        node->left=deserialize(str,index);
        node->right=deserialize(str,index);
        return node;
    }
};

牛客网上可以通过，但实际上可能会有些问题

class Solution {
public:
    char* Serialize(TreeNode *root) {    
       string str;  
       Serialize(root,str);
        int n=str.size();
       char *ret=new char[n+1];
        for(int i=0;i<n;i++)
            ret[i]=str[i];
        ret[n]='\0';
        return ret;
    }
    TreeNode* Deserialize(char *str) {
        if(str==nullptr)
            return nullptr;
        TreeNode *root=Deserialize2(str);
        return root;
    }
    TreeNode *Deserialize2(char *&str){
        
        if(str==nullptr)
            return nullptr;
        
        if(*str=='#'){
            str++;
            return nullptr;
        }
        int num=0;
        while(*str!=',' && *str!='\0')
           { num=num*10+*str-'0';
               str++;
           }
        TreeNode *node=new TreeNode(num);
       if(*str=='\0')
          return node;
        else
            str++;
        node->left=Deserialize2(str);
        node->right=Deserialize2(str);
        return node;
    }
    void Serialize(TreeNode *root,string &str){
        if(root==nullptr)
            {str+='#';
             return ;
            }
        
        str+=to_string(root->val);
        str+=',';
        Serialize(root->left,str);
        Serialize(root->right,str);
    }
};