449. Serialize and Deserialize BST

1.問題

• 設計一個演算法可以對BST做serialize及deserialize.

• 沒有限制演算法有任何限制

• 必須確保BST可以serialize成string, 而且string可以deserialize成BST成原來的結構

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