449. Serialize and Deserialize BST
1. Description
Serialization is 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 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.
2. Example
Example 1:
Input: root = [2,1,3]
Output: [2,1,3]
Example 2:
Input: root = []
Output: []
3. Constraints
- The number of nodes in the tree is in the range [0, $10^4$].
- 0 <= Node.val <= $10^4$
- The input tree is guaranteed to be a binary search tree.
4. Solutions
n is the number of nodes in root
Time complexity: O(n)
Space complexity: O(n)
class Codec {
public:
// Encodes a tree to a single string.
string serialize(TreeNode *root) {
serialize_(root);
return data_;
}
// Decodes your encoded data to tree.
TreeNode *deserialize(string data) {
stringstream stream(data);
vector<int> values;
for (string value; stream >> value;) {
values.push_back(stoi(value));
}
return deserialize_(values, 0, values.size());
}
private:
string data_;
void serialize_(TreeNode *root) {
if (root != nullptr) {
data_.append(to_string(root->val) + ' ');
serialize_(root->left);
serialize_(root->right);
}
}
TreeNode *deserialize_(const vector<int> &values, int beginning, int ending) {
if (beginning < ending) {
TreeNode *root = new TreeNode(values[beginning]);
auto first_bigger_iter = upper_bound(
values.begin() + beginning + 1, values.begin() + ending, values[beginning]);
int first_bigger_index = first_bigger_iter - values.begin();
root->left = deserialize_(values, beginning + 1, first_bigger_index);
root->right = deserialize_(values, first_bigger_index, ending);
return root;
}
return nullptr;
}
};