序列化与反序列化一棵树

public class Code02_SerializeAndReconstructTree_done {    /*     * 二叉树可以通过先序、后序或者按层遍历的方式序列化和反序列化，     * 以下代码全部实现了。     * 但是，二叉树无法通过中序遍历的方式实现序列化和反序列化     * 因为不同的两棵树，可能得到同样的中序序列，即便补了空位置也可能一样。     * 比如如下两棵树     *         __2     *        /     *       1     *       和     *       1__     *          \     *           2     * 补足空位置的中序遍历结果都是{ null, 1, null, 2, null}     *     * */    public static class Node {        public int value;        public Node left;        public Node right;
        public Node(int data) {            this.value = data;        }    }
    //前序  无非就是增加一个queue  把打印的东西存到queue里  空的时候返回空 也保存进去    public static Queue<String> preSerial(Node head) {        Queue<String> queue = new LinkedList<>();        pres(head, queue);        return queue;    }
    public static void pres(Node head, Queue<String> queue) {        if (head == null) {            queue.add(null);            return;        }        queue.add(String.valueOf(head.value));        pres(head.left, queue);        pres(head.right, queue);    }
    //前序 反序列化   返回头节点(队列的第一个出来的元素)    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 temp = prelist.poll();        if (temp == null) {            return null;//挂空        }        Node node = new Node(Integer.valueOf(temp));  //先序列化头        node.left = preb(prelist); //再序列化左右节点        node.right = preb(prelist);        return node;    }
    //后序   无非就是增加一个queue  把打印的东西存到queue里  空的时候返回空 也保存进去    public static Queue<String> posSerial(Node head) {        Queue<String> queue = new LinkedList<>();        poss(head, queue);        return queue;    }
    public static void poss(Node head, Queue<String> queue) {        if (head == null) {            queue.add(null);            return;        }        poss(head.left, queue);        poss(head.right, queue);        queue.add(String.valueOf(head.value));    }
    /*     * 因为左右中的顺序 左下在最前面poll出来 没法按人类逻辑去扩展整棵树(最好是头节点)     * 所以用stack翻转 左右中 => 中右左  反序列化     */    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 temp = posstack.pop();        //递归结束处理        if (temp == null) return null;        Node node = new Node(Integer.valueOf(temp)); // 中右左        node.right = posb(posstack);        node.left = posb(posstack);        return node;    }
    //按层来序列化树     按层遍历的变种, 新增ans来存储, 打印的地方变成ans存储 同时 遇到null 仍然存储    public static Queue<String> levelSerial(Node head) {        LinkedList<String> ans = new LinkedList<>();        //边界处理        if (head == null) {            return null;        } else {            //老套路 用一个queue来暂存下一轮节点(子节点)            LinkedList<Node> queue = new LinkedList<>();            queue.add(head);            ans.add(String.valueOf(head.value));            while (!queue.isEmpty()) {                Node temp = queue.poll();                if (temp.left != null) {  //有左压入左                    queue.add(temp.left);                    ans.add(String.valueOf(temp.left.value));                }else{                    ans.add(null);                }                if (temp.right != null) {                    queue.add(temp.right);                    ans.add(String.valueOf(temp.right.value));                }else{                    ans.add(null);                }            }        }        return ans;    }
    //和按层遍历 类似的逻辑先写出来  得到一个queue<String>  创建一个queue来给下一轮记录状态    // 反序列化逻辑: 先拿到head 再扩展左右节点    // 左右节点非空就压入 到下一轮来扩展  直到queue为空    public static Node buildByLevelQueue(Queue<String> levelList) {        if (levelList == null || levelList.size() == 0) return null;        String headString = levelList.poll();        if (headString == null) return null;        LinkedList<Node> queue = new LinkedList<>();        Node head = new Node(Integer.valueOf(headString));        queue.add(head);//同化处理
        while (!queue.isEmpty()) {            Node temp = queue.poll();            temp.left = generateNode(levelList.poll());            temp.right = generateNode(levelList.poll());            //为下一轮做准备            if(temp.left != null){                queue.add(temp.left);            }            if(temp.right != null){                queue.add(temp.right);            }        }        return head;    }
    public static Node generateNode(String val) {        if (val == null) {            return null;        }        return new Node(Integer.valueOf(val));    }
    // for test    public static Node generateRandomBST(int maxLevel, int maxValue) {        return generate(1, maxLevel, maxValue);    }
    // for test    public static Node generate(int level, int maxLevel, int maxValue) {        if (level > maxLevel || Math.random() < 0.5) {            return null;        }        Node head = new Node((int) (Math.random() * maxValue));        head.left = generate(level + 1, maxLevel, maxValue);        head.right = generate(level + 1, maxLevel, maxValue);        return head;    }
    // for test    public static boolean isSameValueStructure(Node head1, Node head2) {        if (head1 == null && head2 != null) {            return false;        }        if (head1 != null && head2 == null) {            return false;        }        if (head1 == null && head2 == null) {            return true;        }        if (head1.value != head2.value) {            return false;        }        return isSameValueStructure(head1.left, head2.left) && isSameValueStructure(head1.right, head2.right);    }
    // for test    public static void printTree(Node head) {        System.out.println("Binary Tree:");        printInOrder(head, 0, "H", 17);        System.out.println();    }
    public static void printInOrder(Node head, int height, String to, int len) {        if (head == null) {            return;        }        printInOrder(head.right, height + 1, "v", len);        String val = to + head.value + to;        int lenM = val.length();        int lenL = (len - lenM) / 2;        int lenR = len - lenM - lenL;        val = getSpace(lenL) + val + getSpace(lenR);        System.out.println(getSpace(height * len) + val);        printInOrder(head.left, height + 1, "^", len);    }
    public static String getSpace(int num) {        String space = " ";        StringBuffer buf = new StringBuffer("");        for (int i = 0; i < num; i++) {            buf.append(space);        }        return buf.toString();    }
    public static void main(String[] args) {        int maxLevel = 5;        int maxValue = 100;        int testTimes = 1000000;        System.out.println("test begin");        for (int i = 0; i < testTimes; i++) {            Node head = generateRandomBST(maxLevel, maxValue);            Queue<String> pre = preSerial(head);            Queue<String> pos = posSerial(head);            Queue<String> level = levelSerial(head);            Node preBuild = buildByPreQueue(pre);            Node posBuild = buildByPosQueue(pos);            Node levelBuild = buildByLevelQueue(level);            if (!isSameValueStructure(preBuild, posBuild) || !isSameValueStructure(posBuild, levelBuild)) {                System.out.println("Oops!");            }        }        System.out.println("test finish!");
    }}