# 449. Serialize and Deserialize BST

## 1.問題

* 設計一個演算法可以對BST做serialize及deserialize. 
* 沒有限制演算法有任何限制
* 必須確保BST可以serialize成string, 而且string可以deserialize成BST成原來的結構

![](https://901207480-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGKoChvN9am4__HCIRK%2F-LKPGhhRD-6O3WD5HXPX%2F-LKPIj2IgiTA5o9pTkf3%2F%E8%9E%A2%E5%B9%95%E5%BF%AB%E7%85%A7%202018-08-21%20%E4%B8%8A%E5%8D%8810.27.10.png?alt=media\&token=06bfe876-6876-4693-9c8f-4ea0b2814d7c)

## 2.想法

* 1.BST to string:
  * 選擇一種BST traversal方式, 將BST中的元素蒐集到vector中
  * root node 會被列在第一個元素, 後面會依pre-order (VLR)排列
  * 將vector\<int> 轉成string
    * 給予vector起始點地址以及長度
    * 將Vector\<int>轉成char: 對第一個元素取址&後轉型(char\*)

      ```
      int len = sizeof(int) * v.size();
      return string((char *)&v[0], len);
      ```
* 2.string to BST:
  * Recursive:
    * 將curr放到root node
    * 左子: 由於順序是按照pre-order排列, 因此下一個元素一定是左子, 但是有可能下一個元素是某node的右子, 因此如果curr == limit的話就return NULL
    * 右子: 用find\_if找到從curr到limit中, 第一個小於root node的元素, 並接到root node的右子樹
    * 將string轉為int\*: 對第一個元素取址&後轉型(int\*)
      \*

      ````
      ```
      int *x = (int*)&data[0];
      return DoDeserialize(x, x + (data.size() / (sizeof(int))));
      ```
      ````

## 3.程式碼

```
/**
 * 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 (!root) {
            return "";
        }
        vector<int> v;
        DoSerialize(root, v);
        int len = sizeof(int) * v.size();
        return string((char *)&v[0], len);
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if (data.empty()) {
            return NULL;
        }
        int *x = (int*)&data[0];
        return DoDeserialize(x, x + (data.size() / (sizeof(int))));
    }
    
private:
    void DoSerialize(TreeNode *root, vector<int> &ret) {
        if (!root) {
            return;
        }
        ret.push_back(root->val);
        DoSerialize(root->left, ret);
        DoSerialize(root->right, ret);
    }
    
    TreeNode *DoDeserialize(int *cur, int *limit) {
        if (cur == limit) {
            return NULL;
        }
        int val = *cur;
        auto *root = new TreeNode(val);
        int *right = find_if(cur, limit, [val](int i) {
                        return i > val;
                    });
        root->left = DoDeserialize(cur+1, right);
        root->right = DoDeserialize(right, limit);
        return root;
    }
};
// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));
```

## 4.Performance

![](https://901207480-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGKoChvN9am4__HCIRK%2F-LKPGhhRD-6O3WD5HXPX%2F-LKPVYjX8DHn5PUAP7h3%2F%E8%9E%A2%E5%B9%95%E5%BF%AB%E7%85%A7%202018-08-21%20%E4%B8%8A%E5%8D%8811.22.59.png?alt=media\&token=e649f3eb-cddc-46f0-8a05-3bf75cf4b79f)