449. Serialize and Deserialize BST

https://leetcode.com/problems/serialize-and-deserialize-bst/

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，要求生成的字符串尽可能短。序列化普通二叉树需要特殊字符表示null来区分左右子树，BST可利用它自身的性质在preorder遍历时知道遍历到的是左树还是右树从而省去null：值小于parent时说明还在左树，大于时说明在右树。为了进一步压缩空间，将4byte的整数值每一个byte转成一个char，一个结点的值固定对应字符串里的4个char。

空间压缩参考了这。

/*
 * @lc app=leetcode id=449 lang=cpp
 *
 * [449] Serialize and Deserialize BST
 */

// @lc code=start
/**
 * 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:
    void dfs(TreeNode *cur, stringstream &ss) {
        if (cur == nullptr) return;
        char buf[4];
        memcpy(buf, &(cur->val), sizeof(int)); // convert the int into 4 chars
        for (int i = 0; i < 4; ++i) ss << buf[i];
        dfs(cur->left, ss);
        dfs(cur->right, ss);
    }
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        stringstream ss;
        dfs(root, ss);
        return ss.str();
    }

    TreeNode* dfs(vector<int> &preorder, int bound, int &cur) {
        if (cur == preorder.size() || preorder[cur] > bound) return nullptr;
        TreeNode *node = new TreeNode(preorder[cur++]);
        node->left = dfs(preorder, node->val, cur);
        node->right = dfs(preorder, bound, cur);
        return node;
    }
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        string r;
        vector<int> preorder;
        for (int i = 0; i < data.length(); i += sizeof(int)) {
            int value;
            memcpy(&value, &data[i], sizeof(int));
            preorder.push_back(value);
        }
        int cur = 0;
        return dfs(preorder, INT_MAX, cur);
    }
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));
// @lc code=end