449. Serialize and Deserialize BST

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 search tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary search tree can be serialized to a string and this string can be deserialized to the original tree structure.

The encoded string should be as compact as possible.

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

利用到BST的性質的話就不需要給null node用特殊字符代替。

// DFS Pre-Order Traversal
// Preorder Serialization Helper
void serialize(TreeNode* node, ostringstream& os) {
    if (!node) return;
    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();
}

// Preorder Deserialization Helper
TreeNode* deserialize(istringstream& is, int lower, int upper) {
    streampos orig_pos = is.tellg(); // get the current output position in stringstream
    string cur;
    is >> cur;
    if (cur.empty()) return nullptr;
    int val = stoi(cur);
    if (val < lower || val > upper) {
        is.seekg(orig_pos); // reset pos in stringstream 
        return nullptr;
    } 
    TreeNode* root = new TreeNode(val);
    root->left = deserialize(is, lower, val);
    root->right = deserialize(is, val, upper);
    return root;
}

// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
    if (data.empty()) return nullptr;
    istringstream is(data);
    return deserialize(is, INT_MIN, INT_MAX);
}

// DFS Pre-Order Traversal
// Preorder Serialization Helper
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();
}

// Preorder Deserialization Helper
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);
}

// BFS Level Order Traversal
// 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;
}