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.
这道题让我们对二叉搜索树序列化和去序列化，跟之前那道Serialize and Deserialize Binary Tree极其相似，虽然题目中说编码成的字符串要尽可能的紧凑，但是我们并没有发现跟之前那题有何不同，而且也没有看到能够利用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<TreeNode*> 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<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; } };
本文转自博客园Grandyang的博客，原文链接：二叉搜索树的序列化和去序列化[LeetCode] Serialize and Deserialize BST ，如需转载请自行联系原博主。
