題目37：序列化二叉樹

請實(shí)現(xiàn)兩個函數(shù)，分別用來序列化和反序列化二叉樹。
將樹寫入一個文件被稱為“序列化”，讀取文件后重建同樣的二叉樹被稱為“反序列化”。

二叉樹節(jié)點(diǎn)

private static class BinaryTreeNode {
    private int val;
    private BinaryTreeNode left;
    private BinaryTreeNode right;

    public BinaryTreeNode() {
    }
    public BinaryTreeNode(int val) {
        this.val = val;
    }
}

舉例說明

二叉樹

       1
   /     \
  2       3
 /       / \
 4       5  6

按前序遍歷（只有前序遍歷從根節(jié)點(diǎn)開始）系列化之后：

 1,2,4,$,$,$,3,5,$,$,6,$,$,

思路

• 以前的先序和后序遍歷序列重構(gòu)二叉樹存在缺點(diǎn)：

1. 要求二叉樹中沒有數(shù)值相同的結(jié)點(diǎn)
2. 要求整個序列都讀出后才能開始重構(gòu)，如果序列是流式輸入，那么就需要等待序列輸出完畢才能完成二叉樹的重構(gòu)

• 利用先序遍歷

1. node之間用,隔開
2. 保存二叉樹空結(jié)點(diǎn)為$
   利用這樣的序列，就可以規(guī)避上面存在的兩種缺點(diǎn)。

代碼實(shí)現(xiàn)

import java.util.LinkedList;
import java.util.Queue;

public class _37{
    private static class BinaryTreeNode {
        private int value;
        private BinaryTreeNode left;
        private BinaryTreeNode right;

        public BinaryTreeNode() {
        }
        public BinaryTreeNode(int value) {
            this.value = value;
        }
    }


    public static String serialize(BinaryTreeNode root) {
        if (root == null) {
            return "$,";
        }
        String res = root.value + ",";
        res += serialize(root.left);
        res += serialize(root.right);
        return res;
    }

    public static BinaryTreeNode deserialize(String preStr) {
        String[] values = preStr.split(",");//按之前的分隔符，得到一個數(shù)組
        Queue<String> queue = new LinkedList<String>();
        for (int i = 0; i < values.length; i++) {
            queue.offer(values[i]);
        }
        return deserialize(queue);
    }
    
    public static BinaryTreeNode deserialize(Queue<String> queue) {
        String value = queue.poll();//移除并返問隊(duì)列頭部的元素(如果隊(duì)列為空，返回null)
        if (value.equals("$")) {
            return null;
        }//分別遞歸消費(fèi)這個隊(duì)列
        BinaryTreeNode root = new BinaryTreeNode(Integer.valueOf(value));
        root.left = deserialize(queue);
        root.right = deserialize(queue);
        return root;
    }

    public static void main(String[] args) {
        //       1
        //    /    \
        //   2     3
        //  /    / \
        // 4    5  6
        BinaryTreeNode n1 = new BinaryTreeNode(1);
        BinaryTreeNode n2 = new BinaryTreeNode(2);
        BinaryTreeNode n3 = new BinaryTreeNode(3);
        BinaryTreeNode n4 = new BinaryTreeNode(4);
        BinaryTreeNode n5 = new BinaryTreeNode(5);
        BinaryTreeNode n6 = new BinaryTreeNode(6);
        n1.left = n2;
        n1.right = n3;
        n2.left = n4;
        n3.left = n5;
        n3.right = n6;
        
        String result = serialize(n1);
        System.out.println("serialize: "+result);
        BinaryTreeNode root = deserialize(result) ;
        System.out.println("deserialize: ");
        printTree(root);
    }

    public static void printTree(BinaryTreeNode node) {
        if (node != null) {
            System.out.print(node.value + " ");
            printTree(node.left);
            printTree(node.right);
        }
    }
}

序列化二叉樹