###### tags: `LeetCode` `Tree` `Recursion` `Medium`
# LeetCode #449 [Serialize and Deserialize BST](https://leetcode.com/problems/serialize-and-deserialize-bst/)
### (Medium)

---
序列化是將數據結構或對象轉換為一系列位的過程，以便它可以存儲在文件或內存緩衝區中，或通過網絡連接鏈路傳輸，以便稍後在同一個或另一個計算機環境中重建。

設計一個算法來序列化和反序列化 二元搜尋樹 。對序列化/反序列化算法的工作方式沒有限制。您只需確保二元搜尋樹可以序列化為字符串，並且可以將該字符串反序列化為最初的二元搜尋樹。

編碼的字符串應盡可能緊湊。

---
撇除序列化/反序列化, 這題的重點在於如何建立preorder traversal, 以及如何用preorder traversal還原tree。
有一棵樹長這樣, 則它的preorder traversal為 : 5 [2 1 4] [6 8]

可以先處理左子樹[2 1 4]部分, 而當讀取到[6], 該數大於root->val(5)時就知道左子樹處理完了, 此時返回nullptr。

使用遞迴可以很輕鬆地完成整棵樹的重構。

※reinterpret_cast的使用:可以將某個類型的指標轉為另一類型的指標, 因此可以將int的指標轉為char類型的指標, 並append到string中; 反之也可以從string中取出int, 如下:

int val = *reinterpret_cast<const int*>(s.data() + pos);

先用s.data()取得string的指標, 並以pos調整位置(4的倍數), 再用reinterpret_cast將char*轉成int*,最後再加上取值符 "*" 取得整數值並存入val中。

---
LeetCode 版本

class Codec {
public:
 
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string s;
        serialize(root, s);
        return s;
    }
 
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {        
        int pos = 0;
        return deserialize(data, pos, INT_MIN, INT_MAX);
    }
private:
    void serialize(TreeNode* root, string& s) {
        if (!root) return;    
        s.append(reinterpret_cast<const char*>(&root->val), sizeof(root->val));
        serialize(root->left, s);
        serialize(root->right, s);
    }
    
    TreeNode* deserialize(const string& s, int& pos, int curMin, int curMax) {
        if (pos >= s.size()) return nullptr;
        int val = *reinterpret_cast<const int*>(s.data() + pos);
        if (val < curMin || val > curMax) return nullptr;
        pos += sizeof(val);
        TreeNode* root = new TreeNode(val);
        root->left = deserialize(s, pos, curMin, val);
        root->right = deserialize(s, pos, val, curMax);
        return root;
    }
};