package com.freetymekiyan.algorithms.level.hard;

import com.freetymekiyan.algorithms.utils.Utils;
import com.freetymekiyan.algorithms.utils.Utils.TreeNode;

import org.junit.Assert;
import org.junit.Test;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

/**
 * Serialization is the process of converting a data structure or object into a sequence of bits so that it can be
 * stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the
 * same or another computer environment.
 * <p>
 * Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your
 * serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to
 * a string and this string can be deserialized to the original tree structure.
 * <p>
 * For example, you may serialize the following tree
 * <p>
 * |   1
 * |  / \
 * | 2   3
 * |    / \
 * |   4   5
 * as "[1,2,3,null,null,4,5]", just the same as how LeetCode OJ serializes a binary tree. You do not necessarily need to
 * follow this format, so please be creative and come up with different approaches yourself.
 * <p>
 * Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms
 * should be stateless.
 * <p>
 * Company Tags: LinkedIn, Google, Uber, Facebook, Amazon, Microsoft, Yahoo, Bloomberg
 * Tags: Tree, Design
 * Similar Problems: (M) Encode and Decode Strings
 */
public class SerializeAndDeserializeBinaryTree {

    private static final String SPLITER = ",";
    private static final String NULLNODE = "#";

    /**
     * Pre-order traversal with root and a string builder.
     */
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        buildString(root, sb);
        return sb.toString();
    }

    /**
     * Pre-order traversal.
     * => 1,2,#,#,3,4,#,#,5,#,#,
     */
    private void buildString(TreeNode node, StringBuilder sb) {
        if (node == null) {
            sb.append(NULLNODE).append(SPLITER);
            return;
        }
        sb.append(node.val).append(SPLITER);
        buildString(node.left, sb);
        buildString(node.right, sb);
    }

    /**
     * Recursive.
     * Same as pre-order traversal.
     * Split data and create a queue of string values first.
     * Each time, poll a node from the queue, create the current root.
     * Then build left and right subtree recursively.
     */
    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        Deque<String> nodes = new LinkedList<>();
        nodes.addAll(Arrays.asList(data.split(SPLITER)));
        return buildTree(nodes);
    }

    private TreeNode buildTree(Deque<String> nodes) {
        String val = nodes.poll();
        // Get a value from queue and build node
        if (NULLNODE.equals(val)) {
            return null;
        }
        TreeNode node = new TreeNode(Integer.valueOf(val));
        node.left = buildTree(nodes); // Build left subtree
        node.right = buildTree(nodes); // Build right subtree
        return node;
    }

    @Test
    public void testExamples() {
        TreeNode root = Utils.buildBinaryTree(new Integer[]{1, 2, null, null, 3, 4, null, null, 5});
        String s = serialize(root);
        TreeNode newRoot = deserialize(s);
        String s1 = serialize(newRoot);
        Assert.assertEquals(s, s1);
    }
}

@@ -222,17 +222,21 @@
 il.Array
-s
+Deque
 ;%0Aimport
@@ -246,21 +246,22 @@
 va.util.
-Deque
+Arrays
 ;%0Aimport
@@ -271,26 +271,21 @@
 va.util.
-LinkedList
+Deque
 ;%0A%0A/**%0A 
@@ -1604,19 +1604,21 @@
  String 
-SPL
+DELIM
 ITER = %22
@@ -1653,24 +1653,25 @@
  String NULL
+_
 NODE = %22#%22;%0A
@@ -1671,32 +1671,50 @@
 = %22#%22;%0A%0A    /**%0A
+     * Recursive.%0A
      * Pre-order
@@ -1977,24 +1977,35 @@
   /**%0A     *
+ Recursive.
  Pre-order t
@@ -2010,24 +2010,205 @@
  traversal.%0A
+     * Append current node's val and a delimiter.%0A     * Then recurse down to left and right subtrees.%0A     * Base case:%0A     * If node is null, append a null node and a delimiter.%0A
      * =%3E 1,
@@ -2350,24 +2350,25 @@
 .append(NULL
+_
 NODE).append
@@ -2360,35 +2360,37 @@
 LL_NODE).append(
-SPL
+DELIM
 ITER);%0A         
@@ -2445,19 +2445,21 @@
 .append(
-SPL
+DELIM
 ITER);%0A 
@@ -2671,70 +2671,114 @@
   * 
-Each time, poll a node from the queu
+Poll a value string from the queue.%0A     * If null nod
 e, 
-c
 re
-ate the current root
+turn null.%0A     * Create a tree node with value
 .%0A  
@@ -2815,16 +2815,17 @@
  subtree
+s
  recursi
@@ -2965,18 +2965,18 @@
 new 
-LinkedList
+ArrayDeque
 %3C%3E()
@@ -3027,11 +3027,13 @@
 lit(
-SPL
+DELIM
 ITER
@@ -3135,43 +3135,8 @@
 ) %7B%0A
-        String val = nodes.poll();%0A
     
@@ -3179,16 +3179,52 @@
 ild node
+.%0A        String val = nodes.poll();
 %0A       
@@ -3232,16 +3232,17 @@
 if (NULL
+_
 NODE.equ
@@ -3399,32 +3399,33 @@
 ild left subtree
+.
 %0A        node.ri
@@ -3470,16 +3470,17 @@
  subtree
+.
 %0A       

update Serializer And Deserialize Binary Tree