二叉树的序列化和反序列化

3.1 序列化

将内存中的二叉树变为文件中的二叉树，使得文件中的二叉树可以还原成内存中的二叉树。
树和字符串应该是一一对应的，文件中的二叉树应该保存二叉树的结构。
注意中序遍历无法序列化，会有歧义。
序列化就是二叉树遍历方式的改写而已。

3.1.1 按先序方式序列化

1. 按照先序方式遍历，null 不可忽略，用来表示树的结束；
2. 每个节点以逗号为分隔，区分每个节点不同的值；

3.1.2 按层序列化

1. 若为左子节点为空，则只序列化，不入队列；
2. 若左子节点不为空，则序列化并且加入队列；
3. 若头节点为空，就直接返回；

3.2 反序列化

将文件中的二叉树还原成内存中的二叉树。一颗二叉树最重要的地方就是头节点，所以第一步就是找到二叉树的头节点。

3.2.1 先序方式反序列化

利用二叉树的递归套路，我们考虑使用递归实现。对于任意时刻的子树，要构建这棵子树，需要头节点的左右子树。
现在的问题是如何找到子树的头节点？我们考察考察先序遍历的特点，就会发现，先序遍历在第一次遍历到该节点的时候就打印节点，所以假如我们能得到任意状态下，先序遍历的序列，并且从这个序列中得到第一个节点，那么这棵树就好遍历了。
所以，我们将原先的先序遍历的结果放入队列，每想生成一个节点就从队列中弹出，此时队列中弹出的节点就是我们子树的头节点。

public static Node buildByPreQueue(Queue<String> prelist) {  
    if (prelist == null || prelist.size() == 0) {  
        return null;  
    }  
    return preb(prelist);  
}  
  
public static Node preb(Queue<String> prelist) {  
    String value = prelist.poll();  
    if (value == null) {  
        return null;  
    }  
    Node head = new Node(Integer.valueOf(value));  
    head.left = preb(prelist);  
    head.right = preb(prelist);  
    return head;  
}

3.2.2 后序方式反序列化

与先序的思路相同，后序方式的反序列化思路也是抓住了后序遍历的序列中最后一个元素就是二叉树的头节点，所以我们考虑将原序列入栈。
每次生成头节点就从栈中弹出一个元素。

public static Node buildByPosQueue(Queue<String> poslist) {  
    if (poslist == null || poslist.size() == 0) {  
        return null;  
    }  
    // 左右中  ->  stack(中右左)  
    Stack<String> stack = new Stack<>();  
    while (!poslist.isEmpty()) {  
        stack.push(poslist.poll());  
    }  
    return posb(stack);  
}  
  
public static Node posb(Stack<String> posstack) {  
    String value = posstack.pop();  
    if (value == null) {  
        return null;  
    }  
    Node head = new Node(Integer.valueOf(value));  
    head.right = posb(posstack);  
    head.left = posb(posstack);  
    return head;  
}

3.2.3 中序方式反序列化？

注意，中序方式无法反序列化，因为其根节点是无法确定的。举个反例证明：

解读：

1. 可以看到两颗完全不同的二叉树中序序列化的结果竟然是相同的，这充分证明了中序方式是无法反序列化的；