Serialize and Deserialize BST

Question

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.

Solution

第一次寫的時候用了 level-order traversal，但最後沒寫出來。原因是 level order 會遇到不知道如何處理 node 之間的關係，我試著把 null 也加進字串裡看看能否 reconstruct，但最後還是無法 parse。解答用了 pre-order，然後善用 BST 的特性，用 min/max value 去判斷 left 跟 right。

1. 要特別注意 min/max 之間的關係，因為解答就是透過這個特性去限制，才能成功把 BST 重建出來

2. 用 int[] 來做到 pass by address。如果只是傳個 int 進去，因為 java 語言的特性是 pass by value，所以你在函數裡面修改的值，並不會同步回上層，因此也無法在其他地方被用到 ``` public class Codec {

   // Encodes a tree to a single string. public String serialize(TreeNode root) {

    StringBuilder sb  = new StringBuilder();
    buildString(root, sb);
    return sb.toString();
   

   }

   private void buildString(TreeNode t, StringBuilder sb) {

    if (t == null) {
        return;
    }
   
    sb.append(t.val).append(",");
    buildString(t.left, sb);
    buildString(t.right, sb);
   

   }

   // Decodes your encoded data to tree. public TreeNode deserialize(String data) {

    if (data.length() == 0) {
        return null;
    }
   
    int[] pos = new int[1];
    pos[0] = 0;
    return buildTree(data.split(","), pos, Integer.MIN_VALUE, Integer.MAX_VALUE);
   

   }

   private TreeNode buildTree(String[] nodes, int[] pos, int min, int max) {

    if (pos[0] == nodes.length) {
        return null;
    }
   
    int val = Integer.valueOf(nodes[pos[0]]);
    if (val < min || val > max) {
        return null;
    }
    pos[0]++;
    TreeNode curr = new TreeNode(val);
    curr.left = buildTree(nodes, pos, min, val);
    curr.right = buildTree(nodes, pos, val ,max);
    return curr;
   

   } }

```