序列化（serialization）在计算机科学的数据处理中，是指将数据结构或对象状态转换成可取用格式（例如存成文件，存于缓冲，或经由网络中发送），以留待后续在相同或另一台计算机环境中，能恢复原先状态的过程。从一系列字节提取数据结构的反向操作，是反序列化（也称为解编组、deserialization、unmarshalling）。

二叉树的序列化：一棵二叉树变成字符串形式。

二叉树的反序列化：从字符串形式变成一棵唯一确定的树。

public class SerializeAndReconstructTree {
    private static final String SEP = "_"; //分隔符
    private static final String NULL = "#"; //代表空节点的字符

    /*
    前序遍历序列化二叉树
    */
    public static String serialByPre(Node head) {
        StringBuilder res = new StringBuilder(""); //用于拼接字符串
        serialByPre(head, res);
        return res.toString();
    }
    //递归前序遍历的过程中完成序列化
    private static void serialByPre(Node head, StringBuilder res) {
        if (head == null) { //边界条件
            res.append(NULL).append(SEP);
            return;
        }
        res.append(head.value).append(SEP);
        serialByPre(head.left, res);
        serialByPre(head.right, res);
    }
    /*
    基于前序遍历序列化字符串反序列化
    */
    public static Node reconByPreString(String preStr) {
        String[] values = preStr.split(SEP);
        Queue<String> queue = new LinkedList<>(Arrays.asList(values));
        return reconByPreOrder(queue);
    }
    private static Node reconByPreOrder(Queue<String> queue) {
        if (queue.isEmpty()) {
            return null;
        }
        String value = queue.poll();
        if (value.equals(NULL)) {
            return null;
        }
        Node head = new Node(Integer.valueOf(value));
        head.left = reconByPreOrder(queue);
        head.right = reconByPreOrder(queue);
        return head;
    }

    /*
    后续遍历序列化
    */
    public static String serialByPos(Node head) {
        StringBuilder res = new StringBuilder();
        serialByPos(head, res);
        return res.toString();
    }
    private static void serialByPos(Node head, StringBuilder res) {
        if (head == null) {
            res.append(NULL).append(SEP);
            return;
        }
        serialByPos(head.left, res);
        serialByPos(head.right, res);
        res.append(head.value).append(SEP);
    }

    /*
    基于后续序列化字符串反序列化
    */
    public static Node reconByPosString(String posStr) {
        String[] values = posStr.split(SEP);
        LinkedList<String> list = new LinkedList<>(Arrays.asList(values));
        return reconByPosOrder(list);
    }
    //后续遍历是左右根，根节点在最后，所以要从后往前取出元素构建二叉树，而且要先建右子树再建左子树
    private static Node reconByPosOrder(LinkedList<String> list) {
        if (list.isEmpty()) {
            return null;
        }
        String value = list.removeLast(); //从后往前取出元素
        if (value.equals(NULL)) {
            return null;
        }
        Node head = new Node(Integer.valueOf(value));
        head.right = reconByPosOrder(list);
        head.left = reconByPosOrder(list);
        return head;
    }

    /*
    中序遍历序列化
    */
    public static String serialByIn(Node head) {
        StringBuilder res = new StringBuilder();
        serialByIn(head, res);
        return res.toString();
    }
    private static void serialByIn(Node head, StringBuilder res) {
        if (head == null) {
            res.append(NULL).append(SEP);
            return;
        }
        serialByIn(head.left, res);
        res.append(head.value).append(SEP);
        serialByIn(head.right, res);
    }

    /*
    层次遍历序列化
    */
    public static String serialByLevel(Node head) {
        StringBuilder res = new StringBuilder();
        Queue<Node> queue = new LinkedList<>();
        queue.add(head);
        while (!queue.isEmpty()) {
            Node cur = queue.poll();
            if (cur == null) {
                res.append(NULL).append(SEP);
                continue;
            }
            res.append(cur.value).append(SEP);
            queue.add(cur.left);
            queue.add(cur.right);
        }
        return res.toString();
    }
    /*
    基于层次序列化字符串反序列化
    */
    public static Node reconByLevelStr(String levelStr) {
        if (levelStr.isEmpty()) {
            return null;
        }
        String[] values = levelStr.split(SEP);
        if (values[0].equals(NULL)) {
            return null;
        }
        Node head = new Node(Integer.valueOf(values[0])); //层次遍历序列中第一个值是根节点值
        Queue<Node> queue = new LinkedList<>(); //记录父节点
        queue.add(head);
        for (int i = 1; i < values.length; i++) {
            Node parent = queue.poll(); //取出父节点
            String left = values[i++]; //取出父节点对应左孩子值
            if (!left.equals(NULL)) {
                parent.left = new Node(Integer.valueOf(left));
                queue.add(parent.left);
            } else {
                parent.left = null;
            }
            String right = values[i]; //取出父节点对应右孩子值
            if (!right.equals(NULL)) {
                parent.right = new Node(Integer.valueOf(right));
                queue.add(parent.right);
            } else {
                parent.right = null;
            }
        }
        return head;
    }
}

需要注意的是中序序列化的字符串不能反序列化，因为中序遍历的字符串确定不了根节点的位置。

例如对于下面两个二叉树而言

对应的中序序列化结果均为 #_4_#_2_#_1_#_3_#_5_#_

序列化结果不能唯一确定一棵二叉树，所以不能反序列化。

应用：判断一棵二叉树是不是另一棵二叉树的子树。