/**
knakul853
 */
class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {

        ostringstream out;

        serialize( root, out );
        return out.str();

    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {

        istringstream in( data );

        return deserialize( in );

    }

    private:

   void serialize( TreeNode* root, ostringstream& out)
   {
       if( !root ){
           out << "# ";
       }
       else
       {
           out << root->val << " ";
           serialize( root-> left, out);
           serialize( root->right, out);
       }
   }

    TreeNode* deserialize( istringstream& in )
    {
        string s;
        in >> s;
        if ( s == "#")
            return NULL;
        TreeNode* root = new TreeNode( stoi(s));

        root->left = deserialize( in );
        root->right = deserialize( in );

        return root;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));