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

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

package com.harrison.class07;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class Code05_SerializeAndReconstruct {
  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> 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 Queue<String> inSerial(Node head) {
    Queue<String> ans = new LinkedList<>();
    ins(head, ans);
    return ans;
  }
  public static void ins(Node head, Queue<String> ans) {
    if (head == null) {
      ans.add(null);
    } else {
      ins(head.left, ans);
      ans.add(String.valueOf(head.value));
      ins(head.right, ans);
    }
  }
  // 后序方式序列化二叉树
  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 builtByPreQueue(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 Node builtByPosQueue(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> possStack) {
    String value = possStack.pop();
    if (value == null) {
      return null;
    }
    // 左右跟 --> 根右左
    Node head = new Node(Integer.valueOf(value));
    head.right = posb(possStack);
    head.left = posb(possStack);
    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<Node>();
      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 builtByLevelQueue(Queue<String> levelList) {
    if (levelList == null || levelList.size() == 0) {
      return null;
    }
    Node head = generateNode(levelList.poll());
    Queue<Node> queue = new LinkedList<Node>();
    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 generateRandomBST(int maxLevel, int maxValue) {
    return generate(1, maxLevel, maxValue);
  }
  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 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 testTimes = 1000000;
    int maxLevel = 5;
    int maxValue = 100;
    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 preBuilt = builtByPreQueue(pre);
      Node posBuilt = builtByPosQueue(pos);
      Node levleBuilt = builtByLevelQueue(level);
      if (!isSameValueStructure(preBuilt, posBuilt) || !isSameValueStructure(posBuilt, levleBuilt)) {
        System.out.println("oops");
      }
    }
    System.out.println("finish");
  }
}