#define Node TreeNode

class Solution {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string ans;
        dfs_s(ans,root);
       // cout << ans <<endl;
        return ans;
    }
    void dfs_s(string & res, Node * root) {
        if(root == NULL) {
            res += "n ";
            return;
        }
        res += to_string(root ->val)+' ';
        dfs_s(res,root->left);
        dfs_s(res,root->right);

    }
    Node* dfs_d(string &s, int &len) {
        if(len == s.size()) return NULL;
        int k = len;
        while(s[k] !=' ') ++k;
        //数字, 或者 null
        if(s[len]=='n') {
            len = k+1;
            return NULL;
        }
        //数字
        int val=0;
        int flag=1;
        if(s[len]=='-') {
            //处理负数
            len++;
            flag = -1;
        }
        for(int i=len;i<k;++i) val = val*10 + (s[i]-'0');
        Node * cur = new Node(val*flag);
        len = k+1;
        cur->left = dfs_d(s,len);
        cur->right =dfs_d(s,len);
        return cur;
    }
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        int len=0;
        return dfs_d(data,len);
    }
};