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

• 可以用先序或者中序或者后序或者按层遍历，来实现二叉树的序列化
• 用了什么方式序列化，就用什么样的方式反序列化
• 但是，二叉树无法通过中序遍历的方式实现序列化和反序列化
• 所以，二叉树可以通过先序、后序或者按层遍历的方式序列化和反序列化，
• 不同的两棵树，可能得到同样的中序序列，即便补了空位置也可能一样。比如如下两棵树，补足空位置的中序遍历结果都是{ null, 1, null, 2, null}

// __2
// /
// 1
// 和
// 1__
// \
// 2

package com.harrison.class07;

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

/** * @author Harrison * @create 2022-03-09-14:58 * @motto 众里寻他千百度，蓦然回首，那人却在灯火阑珊处。 */
public class Code04_SerializeAndReconstructBT {
    
    public static class Node{
    
        public int value;
        public Node left;
        public Node right;

        public Node(int v){
    
            value=v;
        }
    }

    // 先序序列化
    public static Queue<String> preSerial(Node head){
    
        Queue<String> ans=new LinkedList<>();
        pres(head,ans);
        return ans;
    }

    public static void pres(Node head,Queue<String> ans){
    
        if(head==null){
    
            ans.add(null);
        }else{
    
            ans.add(String.valueOf(head.value));
            pres(head.left,ans);
            pres(head.right,ans);
        }
    }

    // 先序重建
    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;
    }

    // 后序序列化
    public static Queue<String> posSerial(Node head){
    
        Queue<String> ans=new LinkedList<>();
        poss(head,ans);
        return ans;
    }

    public static void poss(Node head,Queue<String> ans){
    
        if(head==null){
    
            ans.add(null);
        }else{
    
            poss(head.left,ans);
            poss(head.right,ans);
            ans.add(String.valueOf(head.value));
        }
    }

    // 后序重建 左右根 -》 根右左
    public static Node buildByPosQueue(Queue<String> posList){
    
        if(posList==null || posList.size()==0){
    
            return null;
        }
        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;
    }

    // 按层序列化
    public static Queue<String> levelSerial(Node head){
    
        Queue<String> ans=new LinkedList<>();
        if(head==null){
    
            ans.add(null);
        }else{
    
            ans.add(String.valueOf(head.value));
            Queue<Node> queue=new LinkedList<>();
            queue.add(head);
            while(!queue.isEmpty()){
    
                head=queue.poll();
                if(head.left!=null){
    
                    ans.add(String.valueOf(head.left.value));
                    queue.add(head.left);
                }else{
    
                    ans.add(null);
                }
                if(head.right!=null){
    
                    ans.add(String.valueOf(head.right.value));
                    queue.add(head.right);
                }else{
    
                    ans.add(null);
                }
            }
        }
        return ans;
    }

    // 按层重建
    public static Node buildByLevelQueue(Queue<String> levelList){
    
        if(levelList==null || levelList.size()==0){
    
            return null;
        }
        Queue<Node> queue=new LinkedList<>();
        Node head=generateNode(levelList.poll());
        if(head!=null){
    
            queue.add(head);
        }
        Node node=null;
        while(!queue.isEmpty()){
    
            node=queue.poll();
            node.left=generateNode(levelList.poll());
            node.right=generateNode(levelList.poll());
            if(node.left!=null){
    
                queue.add(node.left);
            }
            if(node.right!=null){
    
                queue.add(node.right);
            }
        }
        return head;
    }


    public static Node generateNode(String value){
    
        if(value==null){
    
            return null;
        }
        return new Node(Integer.valueOf(value));
    }

    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;
    }

    public static Node generateRandomBST(int maxLevel,int maxValue){
    
        return generate(1,maxLevel,maxValue);
    }

    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);
    }

    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!");

    }
}