package com.jiucaiyuan.net.algrithm.tree;



import java.util.LinkedList;

import java.util.Queue;

import java.util.Stack;



/**

 * 二叉树的序列化与反序列化

 *

 * @Author jiucaiyuan  2022/4/11 22:57

 * @mail services@jiucaiyuan.net

 */

public class SerializeAndDeserializeTree {

    /**

     * 先序遍历-序列化

     * #表示null _表示值结束

     */

    public static String serialByPre(Node root) {

        if (root == null) {

            return "#_";

        }

        String res = root.value + "_";

        res += serialByPre(root.left);

        res += serialByPre(root.right);

        return res;

    }

    /**

     * 先序遍历-反序列化

     * #表示null _表示值结束

     */

    public static Node deSerialByPre(String preStr) {

        String[] values = preStr.split("_");

        Queue<String> queue = new LinkedList<>();

        for(String value:values){

            queue.add(value);

        }

        return deSerialPreOrder(queue);

    }



    private static Node<Integer> deSerialPreOrder(Queue<String> queue) {

        String value = queue.poll();

        if (value.equals("#")){

            return null;

        }

        Node<Integer> node = new Node(Integer.valueOf(value));

        node.left = deSerialPreOrder(queue);

        node.right = deSerialPreOrder(queue);

        return node;

    }



    public static void main (String[] args){

        String preOrder = "1_#_1_1_#_#_#_";

        Node head = deSerialByPre(preOrder);

        PrintBinaryTree.printTree(head);

        System.out.println(serialByPre(head));

        

        String preOrder2 = "1_1_#_1_#_#_#_";

        Node head2 = deSerialByPre(preOrder2);

        PrintBinaryTree.printTree(head2);

        System.out.println(serialByPre(head2));

    }



}