牛客网：序列化二叉树

 

这题说简单点就是让你把一颗二叉树编码成一个字符串，然后根据这个字符串建树。

主要涉及的知识有：

1.二叉树的遍历：按照一定的顺序存储二叉树的值，例如前序，分隔符以及NULL如何表示，然后将一棵二叉树序列化成一个字符串。

2.字符串和string的转化

一点细节：

反序列化（建树）的时候，一开始用了str直接去往后移动，但是这样的*str貌似是个字符串，如果想直接用指针去做，最好用**str，这样在完全解引用之后就是一个字符？也可以直接用位置去做。注意后移的条件有：

1.发现是空指针

2.求值的时候

代码如下所示：

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    void SerializeCore(TreeNode *root,string &str){
        if(root==NULL){
            str+='#';
            return;
        }
        string tmp=to_string(root->val);
        str+=tmp+"!";
        SerializeCore(root->left, str);
        SerializeCore(root->right, str);
    }
    char* Serialize(TreeNode *root) {
        if(root==NULL) return "#";
        string res;
        SerializeCore(root, res);
        char *charRes=new char [res.length()+1];
        strcpy(charRes, res.c_str());
        charRes[res.length()]='\0';
        return charRes;
    }
    TreeNode *DeserializeCore(char *str,int &loc){
        if(str[loc]=='#'){
            loc++;
            return NULL;
        }
        int val=0;
        while(str[loc]!='!' && str[loc]!='\0'){
            val=val*10+((str[loc])-'0');
            loc++;
        }
        TreeNode *root=new TreeNode(val);
        if(str[loc]=='\0'){
            return root;
        }else{
            loc++;
        }
        root->left=DeserializeCore(str, loc);
        root->right=DeserializeCore(str, loc);
        return root;
    }
    TreeNode* Deserialize(char *str) {
        int loc=0;
        return DeserializeCore(str, loc);
    }
};