题目描述

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.

算法1

前序遍历

与序列化和反序列化 二叉树 不同，二叉搜索树 对null leaf 不需要输出”#”，仅用preorder序列即可重建。

例如 [10, 5, 1, 7, 20, 13, 35], 10是root，左子树的大小必然小于10，右子树必然大于10

deserialize时：
(1) 将string 切成vector
(2) 用 &idx 记录递归 处理到了vector的哪个位置
(3) 用 uppder lower 记录当前子树的 可选数字 的范围

时间复杂度 O(n)

C++ 代码

class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        ostringstream oss;
        se(root, oss);
        // cout << oss.str() << endl;
        return oss.str();
    }

    void se(TreeNode* root, ostringstream& oss) {
        if(!root) return;

        oss << root->val << " ";
        se(root->left, oss);
        se(root->right, oss);
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if(data.empty()) return nullptr;

        // convert to int vector
        vector<int> xs;
        istringstream iss(data);
        string t;
        while(iss>>t) { xs.push_back(stoi(t)); }

        int idx = 0;
        return dese(xs, idx, INT_MIN, INT_MAX);
    }

    // 注意 idx用ref，改变递归的全局状态
    TreeNode* dese(const vector<int>& xs, int& idx, int lower, int upper) {
        if(idx>=xs.size() || xs[idx]<=lower || xs[idx]>=upper) return nullptr;

        int val = xs[idx];
        TreeNode* root = new TreeNode(val);

        idx ++;

        root->left = dese(xs, idx, lower, val);
        root->right = dese(xs, idx, val, upper);
        return root;
    }
};