leetcode449.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.

将二叉搜索树序列化和反序列化，序列化是指将树用字符串的形式表示，反序列化是指将字符串形式的树还原成原来的样子。

思路和代码

对于树的序列化，可以直接联想到对树的遍历。树的遍历包括前序遍历，中序遍历，后序遍历和水平遍历，并且可知前序遍历和中序遍历，或中序遍历和后序遍历可以构成一棵唯一的树。除此以外，因为这是一棵二叉搜索树，可知该树的中序遍历就是所有元素的从小到大的排列。

举个例子，假如一棵树的结构如下：

  3
 / \
2   4
 \
  1

该树的前序遍历结果为3,2,1,4，中序遍历为1,2,3,4。再仔细分析前序遍历的结果，结合二叉搜索树可知，比中间节点小的值一定位于左子树，反之一定位于右子树，即可以对前序遍历进行分割3,|2,1,|4。也就是说，我们可以只利用前序遍历，就可以区分出二叉搜索树的左子树和右子树。
代码如下：

public String serialize(TreeNode root) {
    StringBuilder sb = new StringBuilder();
    preorder(root, sb);
    return sb.toString();
}

public void preorder(TreeNode root, StringBuilder result) {
    if(root != null) {
        result.append(root.val);
        result.append(":");
        preorder(root.left, result);
        preorder(root.right, result);
    }
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
    if(data==null || data.isEmpty()) return null;
    String[] preorder = data.split(":");
    String[] inorder = Arrays.copyOf(preorder, preorder.length);
    Arrays.sort(inorder, new Comparator<String>(){

        @Override
        public int compare(String o1, String o2) {
            Integer i1 = Integer.valueOf(o1);
            Integer i2 = Integer.valueOf(o2);
            return i1.compareTo(i2);
        }
        
    });
    
    return build(inorder, preorder, 0, 0, inorder.length);
}

public TreeNode build(String[] inorder, String[] preorder, int inorderStart, int preorderStart, int length) {
    if(length <= 0) return null;
    TreeNode root = new TreeNode(Integer.valueOf(preorder[preorderStart]));
    for(int i = inorderStart ; i < inorderStart+length ; i++) {
        if(inorder[i].equals(preorder[preorderStart])) {
            root.left = build(inorder, preorder, inorderStart, preorderStart+1, i-inorderStart);
            root.right = build(inorder, preorder, i+1, preorderStart+i-inorderStart+1, inorderStart+length-i-1);
            break;
        }
    }
    
    return root;
}

这里的代码是直接使用排序生成了二叉搜索树的中序遍历的结果，并利用先序遍历和中序遍历构造了一棵二叉搜索树。假如二叉搜索树的节点较多，该算法将会占用大量的额外空间。可以只用先序遍历作为构造树的输入，代码如下：

public TreeNode deserialize(String data) {
    if (data==null) return null;
    String[] strs = data.split(":");
    Queue<Integer> q = new LinkedList<>();
    for (String e : strs) {
        q.offer(Integer.parseInt(e));
    }
    return getNode(q);
}

private TreeNode getNode(Queue<Integer> q) {
    if (q.isEmpty()) return null;
    TreeNode root = new TreeNode(q.poll());//root (5)
    Queue<Integer> samllerQueue = new LinkedList<>();
    while (!q.isEmpty() && q.peek() < root.val) {
        samllerQueue.offer(q.poll());
    }
    root.left = getNode(samllerQueue);
    root.right = getNode(q);
    return root;
}