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