剑指offer---序列化二叉树整理

1. 需要注意的知识点：

• 数组名是数组首元素的地址，本身不是一个占有存储空间的变量
• 单引号是char类型，双引号是字符串类型（const char*）
• 取址与引用的区别：取址一般是跟变量一起，没有类型声明，如&a,取a的地址，而引用则必须有类型声明，且必须进行赋值，声明是引用哪个变量。int &a = b;表示a是int 类型的b的引用，若a或者b发生改变，另外一个也发生改变（绑定关系，a变b变，b变a也变）。若引用前加了一个const，如const int &a = b,则只能通过改变原值b使a发生变化，不能直接通过a改变b了。
• 类型* 变量名与类型 *变量名是相同的
• str是一个字符串数组，那char *str表示的是指针类型，指向str的首元素的地址，而char** 表示的是存放首元素地址的地址，可用&str取址。

2. 代码：

/*
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;
        }
        string str;
        //str作为引用，当在函数中发生改变时，在外部对应的str值也会发生改变
        SerializeCore(root,str);
        //str转为char数据，并增加结束标志
        int length = str.length();
        char *cr = new char[length+1];
        for(int i=0;i<length;i++){
            cr[i] = str[i];
        }
        //作为整个char数据结束的标志
        cr[length] = '\0';
        return cr;
    }
    TreeNode* Deserialize(char *str) {
        if(!str){
            return NULL;
        }
        //因为在DeserializeCore中str的值会发生改变，所以需要将char **str,而str是一个char类型的指针，
        //指向首元素的地址，而**str是取址，表示存放首元素地址的地址，所以这里的类型要匹配，只能是&str，而不能是str,否则会报类型不匹配
        return DeserializeCore(&str);
    }
    //str作为引用，当在函数中发生改变时，在外部对应的str值也会发生改变
    void SerializeCore(TreeNode *root, string &str){
        if(!root){
            //当左右子节点中出现空时以#做标志
            str+='#';
            return;
        }
        str += to_string(root->val);
        //加逗号区分子结点SerliazeCore SerializeCore
        str += ',';
        //继续迭代左右子节点
        SerializeCore(root->left, str);
        SerializeCore(root->right, str);
    }
    // 递归时改变了str值使其指向后面的序列，因此要声明为char**
    // 数组名是数组首个元素的地址，本身不是一个占有存储空间的变量，故*str指向的是第一个元素的位置
    //(*str)++即更改了首个元素的位置
    TreeNode* DeserializeCore(char **str){
        // 到达叶节点时，调用两次，都返回null，所以构建完毕，返回父节点的构建
        if((**str) == '#'){
            //str指针后移一位
            (*str)++;
            return NULL;
        }
        // 整个结点的值用，区分，并且以\0作为数组结束的标志
        int num = 0;
        while((**str)!=','&&(**str)!='\0'){
            num = num*10 + ((**str)-'0');
            (*str)++;
        }
        TreeNode* root = new TreeNode(num);
        if ((**str)=='\0'){
            return root;
        }
        else{
            (*str)++;
        }
        
        root->left = DeserializeCore(str);
        root->right = DeserializeCore(str);
        return root;
    }
};

3. 参考链接：

剑指Offer（六十一）：序列化二叉树 https://cuijiahua.com/blog/2018/01/basis_61.html

C++的单引号和双引号区别 https://blog.csdn.net/lqsgd123/article/details/75157929

c++取址与引用的区别 https://blog.csdn.net/passtome/article/details/7937141

C++引用类型 https://www.cnblogs.com/wackelbh/archive/2009/12/29/1984064.html