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

题目：二叉树的序列化

《程序员代码面试指南》第34题 P107 难度：士★☆☆☆

二叉树的序列化就是二叉树被记录成文件的过程，二叉树的反序列化就是通过文件内容重建原来二叉树的过程。

序列化过程：首先假设序列化的结果字符串为str，初始时str=""。如果遇到null节点，就在str的末尾加上"#!"，"#"表示这个节点为空，节点不存在，"!"表示一个值的结束；如果遇到不为空的节点，假设节点值为2，就在str的末尾加上"2!"。

本书介绍了两种序列化和反序列化的实现。

首先是先序遍历，序列化过程如下：

public String serialByPre(Node head) {
    if (head == null) {
        return "#!";
    }
    String res = head.value + "!";
    res += serialByPre(head.left);
    res += serialByPre(head.right);
    return res;
}

可以看出，该过程很简单，基本就是在先序遍历递归的基础上稍作修改。注意返回值的使用。

然后是反序列化的过程：

public Node reconByPreString(String preStr) {
    String[] values = preStr.split("!");
    Queue<String> queue = new LinkedList<String>();
    for (int i = 0; i != values.length; i++) {
        queue.offer(values[i]);
    }
    return reconPreOrder(queue);
}

public Node reconPreOrder(Queue<String> queue) {
    String value = queue.poll();
    if (value.equals("#")) {
        return null;
    }
    Node head = new Node(Integer.valueOf(value));
    head.left = reconPreOrder(queue);
    head.right = reconPreOrder(queue);
    return head;
}

通过队列+递归来实现。先将所有节点逐一插入队列，然后在逐一取出队列元素的同时，通过判断"#"来选择返回空，或是给当前节点的左孩子或右孩子赋值。

注意，首先需要通过"!"将原来的字符串拆解成字符串数组。同时，递归里层的queue弹出了元素，在外层的queue同样有相应的变化。（传值的是引用，内容做了修改，所有为该引用的变量访问的都是同样的内容）

其次是层序遍历，序列化和反序列化都用到队列结构。

序列化：

public String serialByLevel(Node head) {
    if (head == null) {
        return "#!";
    }
    String res = head.value + "!";
    Queue<Node> queue = new LinkedList<Node>();
    queue.offer(head);
    while (!queue.isEmpty()) {
        head = queue.poll();
        if (head.left != null) {
            res += head.left.value + "!";
            queue.offer(head.left);
        } else {
            res += "#!";
        }
        if (head.right != null) {
            res += head.right.value + "!";
            queue.offer(head.right);
        } else {
            res += "#!";
        }
    }
    return res;
}

反序列化：

public Node reconByLevelString(String levelStr) {
    String[] values = levelStr.split("!");
    int index = 0;
    Node head = generateNodeByString(values[index++]);
    Queue<Node> queue = new LinkedList<Node>();
    if (head != null) {
        queue.offer(head);
    }
    Node node = null;
    while (!queue.isEmpty()) {
        node = queue.poll();
        node.left = generateNodeByString(values[index++]);
        node.right = generateNodeByString(values[index++]);
        if (node.left != null) {
            queue.offer(node.left);
        }
        if (node.right != null) {
            queue.offer(node.right);
        }
    }
    return head;
}

public Node generateNodeByString(String val) {
    if (val.equals("#")) {
        return null;
    }
    return new Node(Integer.valueOf(val));
}

对于两种遍历的反序列化，其实都是重做相应的遍历，遇到"#"就生成null节点，先序遍历就停止生成后续子树的过程，层序遍历就不把null节点放到队列中。

算法细节不再赘述，看代码进行理解(⊙o⊙)…