题解 | #序列化二叉树#

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    // 我们采用后续遍历做一下
    // 拿{8,6,10,5,7,9,11}来说
    /*
        NULL 用#号代表,用逗号分隔元素
        所以后续遍历就是 左右中
        #,#,5,#,#,7,6,#,#,9,#,#,11,10,8,
    */
        string s;
    void ser(TreeNode* root, string& s) {
        if(root==nullptr) {
            s.push_back('#');
            s.push_back(',');
            return;
        }

        ser(root->left,s);
        ser(root->right,s);
        s+=to_string(root->val);
        s.push_back(',');

    }

    char* Serialize(TreeNode *root) {    
        ser(root,s);
        cout<<"ser: "<<s<<endl;
        return const_cast<char*>(s.c_str());
    }

    TreeNode* Des(string& s,int& index) {
        // 先拿到当前的元素
        if(index<0) {
            return nullptr;
        }
        if(s[index]=='#') {
            index--;
            index--;
            return nullptr;
        }
        int i = index;
        while(s[i]!=',') {
            i--;
        }
        string tmp = s.substr(i+1,index-i);
        cout<<"tmp: "<<tmp<<" ";
//         int num =0;
        int num = stoi(s.substr(i+1,index-i));
//         cout<<num<<endl;
        index=i-1;
//         cout<<"index: "<< index<<endl;
        TreeNode * root = new TreeNode(num);

        root->right = Des(s, index);
        root->left = Des(s, index);
        return root;
    }

    TreeNode* Deserialize(char *str) {
        string s(str);
        int index = s.size()-2;
        return Des(s, index);
    }


};