package com.binaryTree;

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

public class SerializeAndReconstructTree {

    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data) {
            this.value = data;
        }
    }

    // 先序序列化:将二叉树转化为字符串组成的队列(通过先序实现)
    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);
        }
        queue.add(String.valueOf(head.value));
        pres(head.left,queue);
        pres(head.right,queue);
    }
    // 先序反序列化,将队列中的字符串转化为Node节点对象
    public static Node buildTreeByPres(Queue<String> prelist){
        if (prelist == null || prelist.size() == 0){
            return null;
        }
          String str = prelist.poll();
          if (str == null){
              return null;
          }
          Node head = new Node(Integer.valueOf(str));
          head.left = buildTreeByPres(prelist);
          head.right = buildTreeByPres(prelist);
          return head;
    }
    //后序序列化
     public static Queue<String> posSerial(Node head){
        Queue<String> queue = new LinkedList<>();
        pos(head,queue);
        return queue;
     }
     public static void pos(Node head,Queue<String> queue){
         if (head == null){
             return;
         }
          pos(head.left,queue);
          pos(head.right,queue);
          queue.add(String.valueOf(head));

     }
     // 后序反序列化
    public static Node buildTreeByPos(Queue<String> poslist){
        if (poslist == null || poslist.size() == 0){
            return null;
        }
        // 在序列化的字符串中，后序遍历二叉树的顺序是 左 右 头，但依据字符来后序构建二叉树的顺序应该是 头 右 左
        // 逆序，需要用到栈
        String str = poslist.poll();  //
        if (str == null){
            return null;
        }
        Stack<String> stack = new Stack<>();
        while (!poslist.isEmpty()){
            stack.push(poslist.poll());
        }
      return preb(stack); // 返回 反序列化后形成的头结点
    }
    public static Node preb(Stack<String> stack){
        String str = stack.pop();
        if (str == null){
            return null;
        }
        Node head = new Node(Integer.valueOf(str));
        head.right = preb(stack);
        head.left = preb(stack);
        return head;
    }
}