449. Serialize and Deserialize BST

postorder DFS O(n) serialize O(n) deserialize O(n) space
serialize时是左右中，deserialize的时候是中右左
digit转一字节字符+delimiter

/**
 * 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) {
        return root ? serialize(root->left) + serialize(root->right) + to_string(root->val) + " " : "";
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        istringstream input(data);
        int x;
        vector<int> v;
        while (input >> x) {
            v.push_back(x);
        }
        return insert(v, INT_MIN, INT_MAX);
    }

    // build BST
    TreeNode *insert(vector<int> &v, int mn, int mx) {
        if (v.empty() || v.back() < mn || v.back() > mx) return nullptr;
        auto root = new TreeNode(v.back());
        v.pop_back();
        root->right = insert(v, root->val, mx);
        root->left = insert(v, mn, root->val);
        return root;
    }
};

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

int转4字节字符串，不需要delimiter

/**
 * 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) {
        return root ? serialize(root->left) + serialize(root->right) + toByte(root->val) : "";
    }

    string toByte(int x) {
        string res(4, 0);
        for (int i = 3; i >= 0; --i, x >>= 4) {
            res[i] = x & 15;
        }
        return res;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        vector<int> v;
        for (int i = 0; i < size(data); i += 4) {
            v.push_back(toInt(data, i));
        }
        return insert(v, INT_MIN, INT_MAX);
    }

    int toInt(const string &s, int b) {
        int res = s[b];
        for (int i = 1; i < 4; ++i) {
            res <<= 4; // 注意只左移3次！！
            res |= s[b + i];
        }
        return res;
    }

    // build BST
    TreeNode *insert(vector<int> &v, int mn, int mx) {
        if (v.empty() || v.back() < mn || v.back() > mx) return nullptr;
        auto root = new TreeNode(v.back());
        v.pop_back();
        root->right = insert(v, root->val, mx);
        root->left = insert(v, mn, root->val);
        return root;
    }
};

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

去掉vector

/**
 * 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) {
        return root ? serialize(root->left) + serialize(root->right) + toByte(root->val) : "";
    }

    string toByte(int x) {
        string res(4, 0);
        for (int i = 3; i >= 0; --i, x >>= 4) {
            res[i] = x & 15;
        }
        return res;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        string_view sv{data};
        return insert(sv, INT_MIN, INT_MAX);
    }

    // int toInt(string_view sv) {
    //     int res = 0, n = size(sv);
    //     for (int i = 0, shift = 0; i < 4; ++i, shift += 4) {
    //         res |= (sv[n - i - 1] << shift);
    //     }
    //     return res;
    // }

    int toInt(string_view sv) {
        int res = 0;
        for (int i = 0, shift = 0; i < 4; ++i, shift += 4, sv.remove_suffix(1)) {
            res |= (sv.back() << shift);
        }
        return res;
    }

    // build BST
    TreeNode *insert(string_view &sv, int mn, int mx) {
        if (sv.empty()) return nullptr;
        int v = toInt(sv);
        if (v < mn || v > mx) return nullptr;
        sv.remove_suffix(4);
        auto root = new TreeNode(v);
        root->right = insert(sv, root->val, mx);
        root->left = insert(sv, mn, root->val);
        return root;
    }
};

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

preorder DFS O(n) serialize O(nlogn) deserialize
前序遍历可以唯一确定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) {
        return root ? to_string(root->val) + " " + serialize(root->left) + serialize(root->right) : "";
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        istringstream input(data);
        string token;
        TreeNode dummy_root(INT_MIN); // 为了能让结果在右子树要选择INT_MIN
        while (input >> token) {
            insert(&dummy_root, stoi(token));
        }
        return dummy_root.right;
    }

    // build BST
    TreeNode *insert(TreeNode *root, int val) {
        if (!root) return root;
        if (val < root->val) {
            root->left = root->left ? insert(root->left, val) : new TreeNode(val);
        } else {
            root->right = root->right ? insert(root->right, val) : new TreeNode(val);
        }
        return root;
    }
};

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

/**
 * 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) {
        return root ? to_string(root->val) + " " + serialize(root->left) + serialize(root->right) : "";
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        istringstream input(data);
        string token;
        TreeNode dummy_root(0);
        while (input >> token) {
            if (dummy_root.left) {
                insert(dummy_root.left, stoi(token));
            } else {
                dummy_root.left = new TreeNode(stoi(token));
            }
        }
        return dummy_root.left;
    }

        // build BST
    void insert(TreeNode *root, int val) {
        if (!root) return;
        if (val < root->val) {
            if (root->left) {
                insert(root->left, val);
            } else {
                root->left = new TreeNode(val);
            }
        } else {
            if (root->right) {
                insert(root->right, val);
            } else {
                root->right = new TreeNode(val);
            }
        }
    }
};

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