LeetCode 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.
本题要序列化和反序列化二叉搜索树。因为二叉搜索树属于二叉树，所以可以直接用LeetCode Serialize and Deserialize Binary Tree对普通二叉树的序列化和反序列化方法。但是二叉搜索树又有其特殊性，即左孩子小于等于根节点，根节点小于等于右孩子。所以如果知道树中有哪些数，通过插入的方法就可以构造好二叉搜索树。 首先还是根据层次遍历或者树的先序遍历得到树的序列化表示，那么序列化的第一个数就是根节点了。反序列化时，依次插入后续的节点构成一棵二叉搜索树就好了。但是数值插入的顺序不能乱，比如下图，虽然确定了根节点是1，如果先插入了4号节点，再插入3号节点，则反序列化得到的树就不是原来的树了。为了保证序列化到的数值顺序正确，可以使用层次遍历或者树的先序遍历。
完整代码如下：
[cpp]
class Codec {
public:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
if (root == NULL)return "";
string ans = to_string(root->val);
if (root->left) ans += ","+serialize(root->left);
if (root->right) ans += ","+serialize(root->right);
return ans;
}
void insert(TreeNode* root, TreeNode* node) {
if (node->val < root->val) {
if (root->left == NULL)root->left = node;
else insert(root->left, node);
}
else {
if (root->right == NULL)root->right = node;
else insert(root->right, node);
}
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
if (data == "")return NULL;
TreeNode* root = NULL;
for (int start = 0, end = 0; end <= data.size(); ++end) {
if (data[end] == ‘,’ || end == data.size()) {
TreeNode* node = new TreeNode(atoi(data.substr(start, end – start).c_str()));
if (root == NULL)root = node;
else insert(root, node);
start = end + 1;
}
}
return root;
}
};
[/cpp]
本代码提交AC，用时26MS。]]>
