数据结构与算法-二叉树序列化和反序列化

package com.atchin.datastruct.tree;

import sun.reflect.generics.tree.Tree;

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

public class SerialTree {

    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(1);
        TreeNode treeNode2 = new TreeNode(2);
        TreeNode treeNode3 = new TreeNode(3);
        treeNode.left = treeNode2;
        treeNode.right = treeNode3;

        TreeNode treeNode4 = new TreeNode(4);
        TreeNode treeNode5 = new TreeNode(5);
        treeNode2.left = null;
        treeNode2.right = treeNode5;

        TreeNode treeNode6 = new TreeNode(6);
        TreeNode treeNode7 = new TreeNode(7);
        treeNode3.left = treeNode6;
        treeNode3.right = null;
        
        levelSerial(treeNode);
    }

    // 先序序列化
    public static Queue<String> preSerial(TreeNode node){
        Queue<String> queue = new LinkedList<>();
        pres(node,queue);
        return queue;
    }

    public static void pres(TreeNode node, Queue<String> queue){
        if(node == null){
            queue.add(null);
        }else{
            queue.add(String.valueOf(node.val));
            pres(node.left,queue);
            pres(node.right,queue);
        }
    }

    // 先序反序列化
    public static TreeNode buildByQueue(Queue<String> prelist){
        if(prelist == null || prelist.size() == 0){
            return null;
        }

        return preb(prelist);
    }

    public static TreeNode preb(Queue<String> preList){
        String value = preList.poll();
        if (null == value){
            return null;
        }

        TreeNode node = new TreeNode(Integer.valueOf(value));
        node.left = preb(preList);
        node.right = preb(preList);

        return node;
    }


    // 按层级序列化  不要忽略空节点
    public static Queue<String> levelSerial(TreeNode head){
        if(null == head){
            return null;
        }
        
        Queue<TreeNode> queue = new LinkedList<>();    // 该队列支持层级遍历
        Queue<String> queueSri = new LinkedList<>();   // 该队列支持序列化
        queue.add(head);
        queueSri.add(String.valueOf(head.val));

        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            if(node.left != null){
                queue.add(node.left);
                queueSri.add(String.valueOf(node.left.val));
            }else{
                queueSri.add(null);
            }

            if(node.right != null){
                queue.add(node.right);
                queueSri.add(String.valueOf(node.right.val));
            }else{
                queueSri.add(null);
            }
        }
        
        return queueSri;
    }

    // 按层级反序列化  不要忽略空节点
    public static TreeNode buildByLevelQueue(Queue<String> levelList){
        if (null == levelList || levelList.size() == 0){
            return null;
        }

        TreeNode head = generateNode(levelList.poll());
        Queue<TreeNode> queue = new LinkedList<>();
        if(null != head){
            queue.add(head);
        }

        TreeNode 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 TreeNode generateNode(String val){
        if(null == val){
            return null;
        }

        return new TreeNode(Integer.valueOf(val));
    }

    static class TreeNode{
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
        public TreeNode(int val) {
            this.val = val;
        }
    }
}