Serialize and Deserialize BST

Nov 07, 2019

Serialize and Deserialize BST


今天的题是[](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.



  • 如何序列化一个正常节点
  • 如何序列化一个NULL节点


struct {
	char flag = 'Y';
	union INT {
		int iv;
		char cv[4];




class Codec {
    union INT {
        int iv;
        unsigned char cv[4];
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string str;
        serialize(root, str);
        return str;
    void serialize(TreeNode *root, string &str) {
        if (root == NULL) {
        INT val;
        val.iv = root->val;
        for(int i = 0;i < 4;i++) { 
        serialize(root->left, str);
        serialize(root->right, str);

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        int index = 0;
        return deserialize(data, index);
    TreeNode *deserialize(string &data, int &index) {
        if (index >= data.size() || data[index] == 'N') {
            index += 1;
            return nullptr;  
        index += 1;
        INT val;
        for(int i = 0;i < 4;i++)[i] = (unsigned char)data[index + i];
        index += 4;
        TreeNode *root = new TreeNode(val.iv);
        root->left = deserialize(data, index);
        root->right = deserialize(data, index);
        return root;

Decode String

K Closest Points to Origin

comments powered by Disqus