449. Serialize and Deserialize BST ----M ~~~~~~!!!!!

Serialization is 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 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.

 

Example 1:

Input: root = [2,1,3]
Output: [2,1,3]

Example 2:

Input: root = []
Output: []

 

Constraints:

• The number of nodes in the tree is in the range [0, 104].
• 0 <= Node.val <= 104
• The input tree is guaranteed to be a binary search tree.

A:

就是类似于递归的写法。然而不是最优的。 没有利用BST这个性质。

我还是多加了 ",#" 来代表  nullptr。 然而其实并不需要

/**
 * 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 {
public:
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string res = helper(root);
        // remove the last ',' and '#'
        int end = res.size()-1;
        while(end>=0 && not isdigit(res[end])){
            end--;
        }
        return res.substr(0,end+1);
    }
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        vector<string> tokens;
        // stringstream class check1 
        stringstream check1(data); 
        string tmp; 
        // Tokenizing w.r.t.  ',' 
        while(getline(check1, tmp, ',')) { 
            tokens.push_back(tmp); 
        }
        reverse(tokens.begin(), tokens.end());
        return helper2(tokens);
    }
private:
    string helper(TreeNode* root){
        if(root == nullptr)
            return "#";
        string res = to_string(root->val);
        string left = helper(root->left);
        string right = helper(root->right);
        res+= ","+left + ","+right;
        return res;
    }
    TreeNode* helper2(vector<string>& tokens){
        if(tokens.empty()){
            return nullptr;
        }
        string str = tokens.back();
        tokens.pop_back();
        if(str=="#"){
            return nullptr;
        }
        TreeNode* root = new TreeNode(stoi(str));
        root->left = helper2(tokens);
        root->right = helper2(tokens);
        return root;
    }
};

// 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;

上面的不是最优的，因此，我们这里改了一下， 利用了  BST

/**
 * 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 {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if(not root){
            return "";
        }
        string res = to_string(root->val);
        if(root->left){
            res+= " "+serialize(root->left);
        }
        if(root->right){
            res += " "+serialize(root->right);
        }
        return res;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        vector<int> tokens;
        // stringstream class check1 
        stringstream check1(data); 
        string tmp; 
        // Tokenizing w.r.t.  ' ' 
        while(getline(check1, tmp, ' ')) { 
            tokens.push_back(stoi(tmp)); 
        }
        reverse(tokens.begin(), tokens.end());
        return helper(tokens);
    }
private:
    TreeNode* helper(vector<int>& tokens){
        if(tokens.size() == 0){
            return nullptr;
        }
        TreeNode* root = new TreeNode(tokens.back());
        tokens.pop_back();
        vector<int> sLeft;
        while(not tokens.empty() && tokens.back() < root->val){
            sLeft.push_back(tokens.back());
            tokens.pop_back();
        }
        reverse(sLeft.begin(), sLeft.end()); // need to make to reverse again
        root->left = helper(sLeft);
        root->right = helper(tokens);
        return root;
    }
};

Errors:

忘了这一句：     reverse(sLeft.begin(), sLeft.end()); // need to make to reverse again

How to make the encoded string as compact as possible

This question is similar to the Google interview question discussed last week.

To serialize a binary tree means to

• Encode tree structure.

• Encode node values.

• Choose delimiters to separate the values in the encoded string.

Hence there are three axes of optimisation here.

---

Approach 1: Postorder traversal to optimise space for the tree structure.

Intuition

Let's use here the fact that BST could be constructed from preorder or postorder traversal only. Please check this article for the detailed discussion. In brief, it's a consequence of two facts:

• Binary tree could be constructed from preorder/postorder and inorder traversal.

• Inorder traversal of BST is an array sorted in the ascending order: inorder = sorted(preorder).

That means that BST structure is already encoded in the preorder or postorder traversal and hence they are both suitable for the compact serialization.

Serialization could be easily implemented with both strategies, but for optimal deserialization better to choose the postorder traversal because member/global/static variables are not allowed here.

Implementation

Approach 2: Convert int to 4-bytes string to optimize space for node values.

Intuition

Approach 1 works fine with the small node values but starts to consume more and more space in the case of large ones.

For example, the tree [2,null,3,null,4] is encoded as a string "4 3 2" which uses 5 bytes to store the values and delimiters, 1 byte per value or delimiter. So far everything is fine.

Let's consider now the tree [12345,null,12346,null,12347] which is encoded as "12347 12346 12345" and consumes 17 bytes to store 3 integers and 2 delimiters, 15 bytes for node values only. At the same time it's known that 4 bytes is enough to store an int value, i.e. 12 bytes should be enough for 3 integers. 15 > 12 and hence the storage of values could be optimised.

How to do it? Convert each integer into 4-bytes string.

Implementation