/*

struct TreeNode {

    int val;

    struct TreeNode *left;

    struct TreeNode *right;

    TreeNode(int x) :

            val(x), left(NULL), right(NULL) {

    }

};

*/

class Solution {

public:

    //序列化

    void do_Serialize(TreeNode *root, string &s)

    {

        if(root == nullptr)

        {

            s += '#';

            s += ',';

            return;

        }

        //std::to_string() 数值转换字符串

        s += to_string(root->val);

        s += ',';

        do_Serialize(root->left,s);

        do_Serialize(root->right,s);

    }

    char* Serialize(TreeNode *root)

    {

        if(root == nullptr)

        {

            return nullptr;

        }

        string str = "";

        do_Serialize(root,str);

        //返回值是char *

        char *ret = new char[str.length() + 1]; //'\0'

        strcpy(ret, str.c_str());

        return ret;

    }

    //反序列化

    TreeNode* do_Deserialize(string &s)

    {

        if(s.empty())

        {

            return nullptr;

        }

        if (s[0] == '#')

        {

            s = s.substr(2);    //从s中去掉#,

            return nullptr;

        }

        TreeNode *ret = new TreeNode(stoi(s));

        s = s.substr(s.find_first_of(',') + 1);

        ret->left = do_Deserialize(s);

        ret->right = do_Deserialize(s);

        return ret;

    }

    TreeNode* Deserialize(char *str)

    {

        if(str == nullptr)

        {

            return nullptr;

        }

        string s(str);

        return do_Deserialize(s);

    }

};