题目

序列化是将数据结构或对象转换为一系列位的过程，以便它可以存储在文件或内存缓冲区中，或通过网络连接链路传输，以便稍后在同一个或另一个计算机环境中重建。
设计一个算法来序列化和反序列化 二叉搜索树 。对序列化/反序列化算法的工作方式没有限制。您只需确保二叉搜索树可以序列化为字符串，并且可以将该字符串反序列化为最初的二叉搜索树。
编码的字符串应尽可能紧凑。

示例：

输入：root = [2,1,3]
输出：[2,1,3]

输入：root = []
输出：[]

解答 & 代码

利用二叉搜索树的性质，可以避免序列化空指针，实现更紧凑的编码

解法一：先序 + 中序构建二叉树

本题是二叉搜索树，因此可以借助二叉搜索树的性质，实现更紧凑的编码
二叉搜索树的性质：二叉搜索树的中序遍历序列是递增序列
因此，

编码：只需编码得到二叉搜索树的先序遍历序列即可（无需编码空指针）

解码：将先序遍历序列按升序排序，就得到了二叉搜索树的中序遍历序列，根绝先序遍历序列和中序遍历序列重建二叉树 ```cpp /**

Definition for a binary tree node.
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}

}; */ class Codec { private: unordered_map inOrderMap; // key = 节点值，val = 中序遍历序列中的下标

// 递归由先序和中序遍历序列构建二叉树 TreeNode* dfsBuildTree(vector& preOrder, int preStart, int preEnd, int inStart, int inEnd) {

if(preStart > preEnd)
    return NULL;
int rootVal = preOrder[preStart];
TreeNode* root = new TreeNode(rootVal);
int InOrderRootIdx = inOrderMap[rootVal];
int leftLen = InOrderRootIdx - inStart;
root->left = dfsBuildTree(preOrder, preStart + 1, preStart + leftLen, inStart, InOrderRootIdx - 1);
root->right = dfsBuildTree(preOrder, preStart + leftLen + 1, preEnd, InOrderRootIdx + 1, inEnd);
return root;

} public:

// Encodes a tree to a single string. // 编码得到二叉树的先序遍历序列字符串，数值之间用空格隔开 string serialize(TreeNode* root) {

if(root == NULL)
    return "";
string result;
result += to_string(root->val);
if(root->left != NULL)
    result += " " + serialize(root->left);
if(root->right != NULL)
    result += " " + serialize(root->right);
return result;

}

// Decodes your encoded data to tree. TreeNode* deserialize(string data) {

istringstream istr(data);
vector<int> preOrder;                // 先序遍历数组
string val;
while(istr >> val)
    preOrder.push_back(stoi(val));
vector<int> inOrder = preOrder;        // 中序遍历数组（先序遍历数组升序排序得到）
sort(inOrder.begin(), inOrder.end());
for(int i = 0; i < inOrder.size(); ++i)
    inOrderMap[inOrder[i]] = i;
// 递归由先序和中序遍历序列构建二叉树
return dfsBuildTree(preOrder, 0, preOrder.size() - 1, 0, inOrder.size() - 1);

} };

// Your Codec object will be instantiated and called as such: // Codec ser = new Codec(); // Codec deser = new Codec(); // string tree = ser->serialize(root); // TreeNode* ans = deser->deserialize(tree); // return ans;

复杂度分析：设二叉树节点数为 N
- 时间复杂度 O(N)：
- 空间复杂度 O(N)：
执行结果：

执行结果：通过

执行用时：32 ms, 在所有 C++ 提交中击败了 62.15% 的用户内存消耗：30.9 MB, 在所有 C++ 提交中击败了 20.38% 的用户


<a name="UyKjT"></a>
## 解法二：先序序列构建二叉搜索树
可以利用**二叉搜索树的另一个性质：根节点的值大于所有左子树节点的值，小于所有右子树节点的值**<br />因此，
- **编码**：只需编码得到二叉搜索树的**先序遍历**序列即可（无需编码空指针）
- **解码**：递归用先序遍历序列，以及节点值范围构建二叉搜索树
```cpp
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
private:
    // 利用先序遍历序列和节点取值范围，递归构建二叉搜索树
    TreeNode* dfsBuildBST(deque<int>& preOrderQ, int minVal, int maxVal)
    {
        // 递归结束条件 1：如果序列为空，则返回 NULL
        if(preOrderQ.size() == 0)
            return NULL;
        // 递归结束条件 2：如果根节点的值不在限定的上下界范围内，则返回 NULL
        int rootVal = preOrderQ.front();
        if(rootVal <= minVal || rootVal >= maxVal)
            return NULL;
        preOrderQ.pop_front();                        // 弹出根节点
        TreeNode* root = new TreeNode(rootVal);        // 构建根节点
        // 递归构建左、右子树（收缩节点的取值范围）
        root->left = dfsBuildBST(preOrderQ, minVal, rootVal);
        root->right = dfsBuildBST(preOrderQ, rootVal, maxVal);
        return root;                                // 返回根节点
    }
public:
    // Encodes a tree to a single string.
    // 编码得到二叉树的先序遍历序列字符串，数值之间用空格隔开
    string serialize(TreeNode* root) {
        if(root == NULL)
            return "";
        string result;
        result += to_string(root->val);
        if(root->left != NULL)
            result += " " + serialize(root->left);
        if(root->right != NULL)
            result += " " + serialize(root->right);
        return result;
    }
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        // cout << data << endl;
        istringstream istr(data);
        deque<int> preOrderQ;    // 双端队列，记录先序遍历序列
        string val;
        while(istr >> val)
            preOrderQ.push_back(stoi(val));
        return dfsBuildBST(preOrderQ, INT_MIN, INT_MAX);
    }
};
// Your Codec object will be instantiated and called as such:
// Codec* ser = new Codec();
// Codec* deser = new Codec();
// string tree = ser->serialize(root);
// TreeNode* ans = deser->deserialize(tree);
// return ans;

复杂度分析：设二叉树节点数为 N

时间复杂度 O(N)：
空间复杂度 O(N)：

执行结果：

执行结果：通过
执行用时：36 ms, 在所有 C++ 提交中击败了 43.44% 的用户
内存消耗：29.9 MB, 在所有 C++ 提交中击败了 23.04% 的用户

hot 100

[中等] 449. 序列化和反序列化二叉搜索树

题目

解答 & 代码

解法一：先序 + 中序构建二叉树