297. Serialize and Deserialize Binary Tree

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

Example:

You may serialize the following tree:

    1
   / \
  2   3
     / \
    4   5

as "[1,2,3,null,null,4,5]"

Clarification: The above format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

// Encodes a tree to a single string.
string serialize(TreeNode* root) {
    if (!root) return "";
    ostringstream os;
    queue<TreeNode*> q({root});
    while (!q.empty()) {
        TreeNode* t = q.front(); q.pop();
        if (!t) {
            os << "# ";
        } else {
            os << to_string(t->val) << " ";
            q.push(t->left);
            q.push(t->right);
        }
    }
    return os.str();
}

// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
    if (data.empty()) return nullptr;
    istringstream is(data);
    queue<TreeNode*> q;
    string val;
    is >> val;
    TreeNode* res = new TreeNode(stoi(val)), *cur = res;
    q.push(cur);
    while (!q.empty()) {
        TreeNode* t = q.front(); q.pop();
        if (!(is >> val)) break;
        if (val != "#") {
            cur = new TreeNode(stoi(val));
            q.push(cur);
            t->left = cur;
        }
        if (!(is >> val)) break;
        if (val != "#") {
            cur = new TreeNode(stoi(val));
            q.push(cur);
            t->right = cur;
        }
    }
    return res;
}

// Preorder Traversal
void serialize(TreeNode* node, ostringstream& os) {
    if (!node) {
        os << "# ";
    } else {
        os << to_string(node->val) << " ";
        serialize(node->left, os);
        serialize(node->right, os);
    }
}
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
    ostringstream os;
    serialize(root, os);
    return os.str();
}

TreeNode* deserialize(istringstream& is) {
    string val;
    is >> val;
    if (val == "#") return nullptr;
    TreeNode* root = new TreeNode(stoi(val));
    root->left = deserialize(is);
    root->right = deserialize(is);
    return root;
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
    istringstream is(data);
    return deserialize(is);
}