[LeetCode] 449. Serialize and Deserialize BST

[grandyang]

 

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.

 

这道题让我们对二叉搜索树序列化和去序列化，跟之前那道Serialize and Deserialize Binary Tree极其相似，虽然题目中说编码成的字符串要尽可能的紧凑，但是我们并没有发现跟之前那题有何不同，而且也没有看到能够利用BST性质的方法，姑且就按照之前题目的解法来写吧：

 

解法一：

class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
         ostringstream os;
         serialize(root, os);
         return os.str();
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        istringstream is(data);
        return deserialize(is);
    }
    
    void serialize(TreeNode* root, ostringstream& os) {
        if (!root) os << "# ";
        else {
            os << root->val << " ";
            serialize(root->left, os);
            serialize(root->right, os);
        }
    }
    
    TreeNode* deserialize(istringstream& is) {
        string val = "";
        is >> val;
        if (val == "#") return NULL;
        TreeNode* node = new TreeNode(stoi(val));
        node->left = deserialize(is);
        node->right = deserialize(is);
        return node;
    }
};

 

另一种方法是层序遍历的非递归解法，这种方法略微复杂一些，我们需要借助queue来做，本质是BFS算法，也不是很难理解，就是BFS算法的常规套路稍作修改即可，参见代码如下：

 

解法二：

class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if (!root) return "";
        ostringstream os;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            TreeNode *t = q.front(); q.pop();
            if (t) {
            os << t->val << " ";
            q.push(t->left);
            q.push(t->right);
            } else {
                os << "# ";
            }
        }
        return os.str();
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if (data.empty()) return NULL;
        istringstream is(data);
        queue<TreeNode*> q;
        string val = "";
        is >> val;
        TreeNode *res = new TreeNode(stoi(val)), *cur = res;
        q.push(cur);
        while (!q.empty()) {
            TreeNode *t = q.front(); q.pop();
            if (!(is >> val)) break;
            if (val != "#") {
                cur = new TreeNode(stoi(val));
                q.push(cur);
                t->left = cur;
            }
            if (!(is >> val)) break;
            if (val != "#") {
                cur = new TreeNode(stoi(val));
                q.push(cur);
                t->right = cur;
            }
        }
        return res;
    }
};

 

类似题目：

Serialize and Deserialize Binary Tree

Find Duplicate Subtrees

Serialize and Deserialize N-ary Tree

 

参考资料：

https://leetcode.com/problems/serialize-and-deserialize-bst

https://leetcode.com/problems/serialize-and-deserialize-bst/discuss/93260/easy-bfs-java

 

LeetCode All in One 题目讲解汇总(持续更新中...)

[lld2006]

在discussion看到高票帖子学到的。
利用BST的性质以及前序访问， 可以省去所有nullptr对应的”#“， 做到尽可能的compact。
做了一点点改动， 因为我们总是先访问左子树，再访问右子树， 所以不存在value< low的情况，
所以原代码中if(value > high || value < low) return nullptr; 可以改为
if(value > high) return nullptr；see //####

class Codec {
  public:
  // Encodes a tree to a single string.
  string serialize(TreeNode* root) {
    string ret;
    serialize(root, ret);
    return ret;
  }

  // Decodes your encoded data to tree.
  TreeNode* deserialize(string data) {
    istringstream iss(data);
    queue<int> q;
    string s;
    while(iss>>s) q.push(stoi(s));
    return deserialize(q, numeric_limits<int>::min(), numeric_limits<int>::max());
  }
  TreeNode* deserialize(queue<int>& q, int low, int high){
    if(q.empty()) return nullptr;
    int value = q.front();
    if(value > high) return nullptr;
    // ### no need to compare low since right child tree will always be visited after left child tree
    q.pop();
    TreeNode* root = new TreeNode(value);
    root->left = deserialize(q, low, value);
    root->right = deserialize(q, value, high);
    return root;
  }
  void serialize(TreeNode* node, string& s){
    if(node==nullptr) return;
    s += to_string(node->val)+ " ";
    serialize(node->left, s);
    serialize(node->right,s);
  }
};