/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        stringstream ss;
        run(root, ss);
        std::cout << ss.str() << endl;
        return ss.str();
    }
    void run(TreeNode* root, stringstream& ss)
    {
        if (root)
        {
            ss << root -> val << " ";
            run(root -> left, ss);
            run(root -> right, ss);
        }
        else
        {
            ss << "# ";
        }
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        queue<string> Q;
        const char *ss = data.c_str();
        char*s = const_cast<char*> (ss);
        const char *sep = " "; 
        char *p;
        p = strtok(s, sep);
        while(p) {
            string tmp(p);
            if (!tmp.empty())
                Q.push(tmp);
            p = strtok(NULL, sep);
        }

        return build(Q);
    }
    TreeNode* build(queue<string>& Q)
    {
        if (Q.size() == 0)
            return NULL;
        string tmp = Q.front();
        Q.pop();
        if (tmp == "#")
            return NULL;
        else
        {
            TreeNode* n = new TreeNode(stoi(tmp)); 
            n -> left = build(Q);
            n -> right = build(Q); 
            return n;
        }
    }
};