class Solution {
public:
    char* Serialize(TreeNode* root) {
        tree.clear();
        PreTrav(tree, root);
        return const_cast<char*>(tree.c_str());
    }
    TreeNode* Deserialize(char* str) {
        if (!str) return nullptr;
        TreeNode* result = nullptr;
        result = Build(str, result);
        return result;
    }
private:
    string tree="";
    void PreTrav(string& tree, TreeNode* root)
    {
        if (!root)
        {
            tree.append("#");
            return;
        }
        tree.append(to_string(root->val).append("!"));
        PreTrav(tree, root->left);
        PreTrav(tree, root->right);
    }
    TreeNode* Build(char* &str, TreeNode* node)
    {
        if (!str || *str == '\0') return nullptr;
        if (*str == '#')
        {
            ++str;
            return nullptr;
        }
        node = new TreeNode(-1);
        char* begin = str;
        while (*str != '!') ++str;
        string tmp(begin, str-begin);
        node->val = atoi(tmp.c_str());
        ++str;
        node->left = Build(str, node->left);
        node->right = Build(str, node->right);
        return node;
    }
};