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性质的方法，姑且就按照之前题目的解法来写吧：

 

解法一：

class Codec {public:    // Encodes a tree to a single string.    string serialize(TreeNode* root) {         ostringstream os;         serialize(root, os);         return os.str();    }    // Decodes your encoded data to tree.    TreeNode* deserialize(string data) {        istringstream is(data);        return deserialize(is);    }        void serialize(TreeNode* root, ostringstream& os) {        if (!root) os << "# ";        else {            os << root->val << " ";            serialize(root->left, os);            serialize(root->right, os);        }    }        TreeNode* deserialize(istringstream& is) {        string val = "";        is >> val;        if (val == "#") return NULL;        TreeNode* node = new TreeNode(stoi(val));        node->left = deserialize(is);        node->right = deserialize(is);        return node;    }};

 

另一种方法是层序遍历的非递归解法，这种方法略微复杂一些，我们需要借助queue来做，本质是BFS算法，也不是很难理解，就是BFS算法的常规套路稍作修改即可，参见代码如下：

 

解法二：

class Codec {public:    // Encodes a tree to a single string.    string serialize(TreeNode* root) {        if (!root) return "";        ostringstream os;        queue
     
       q;        q.push(root);        while (!q.empty()) {            TreeNode *t = q.front(); q.pop();            if (t) {            os << t->val << " ";            q.push(t->left);            q.push(t->right);            } else {                os << "# ";            }        }        return os.str();    }    // Decodes your encoded data to tree.    TreeNode* deserialize(string data) {        if (data.empty()) return NULL;        istringstream is(data);        queue
      
        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;    }};
      
     

 

类似题目：

 

参考资料：