package com.fishercoder.solutions;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 331. Verify Preorder Serialization of a Binary Tree
 *
 * One way to serialize a binary tree is to use pre-order traversal. When we encounter a non-null node, we record the node's value. If it is a null node, we record using a sentinel value such as #.

       _9_
      /    \
     3     2
    / \   / \
   4  1  #  6
  / \ / \  / \
  # # # #  # #

 For example, the above binary tree can be serialized to the string "9,3,4,#,#,1,#,#,2,#,6,#,#", where # represents a null node.

 Given a string of comma separated values, verify whether it is a correct preorder traversal serialization of a binary tree. Find an algorithm without reconstructing the tree.

 Each comma separated value in the string must be either an integer or a character '#' representing null pointer.

 You may assume that the input format is always valid, for example it could never contain two consecutive commas such as "1,,3".

 Example 1:
 "9,3,4,#,#,1,#,#,2,#,6,#,#"
 Return true

 Example 2:
 "1,#"
 Return false

 Example 3:
 "9,#,#,1"
 Return false


 */
public class _331 {

    public static class Solution1 {
        public boolean isValidSerialization(String preorder) {
            /**Idea: we keep inserting the string into the stack, if it's a number, we just push it onto the stack;
             * if it's a "#", we see if the top of the stack is a "#" or not,
             * 1. if it's a "#", we pop it and keep popping numbers from the stack,
             * 2. if it's not a "#", we push the "#" onto the stack*/
            if (preorder == null || preorder.length() == 0) {
                return false;
            }
            String[] pre = preorder.split(",");
            Deque<String> stack = new ArrayDeque<>();
            for (int i = 0; i < pre.length; i++) {
                while (pre[i].equals("#") && !stack.isEmpty() && stack.peekLast().equals("#")) {
                    stack.pollLast();
                    if (stack.isEmpty()) {
                        return false;
                    }
                    stack.pollLast();
                }
                stack.addLast(pre[i]);
            }
            return stack.size() == 1 && stack.peekLast().equals("#");
        }
    }

}

@@ -87,1049 +87,8 @@
 e;%0A%0A
-/**%0A * 331. Verify Preorder Serialization of a Binary Tree%0A *%0A * One way to serialize a binary tree is to use pre-order traversal. When we encounter a non-null node, we record the node's value. If it is a null node, we record using a sentinel value such as #.%0A%0A       _9_%0A      /    %5C%0A     3     2%0A    / %5C   / %5C%0A   4  1  #  6%0A  / %5C / %5C  / %5C%0A  # # # #  # #%0A%0A For example, the above binary tree can be serialized to the string %229,3,4,#,#,1,#,#,2,#,6,#,#%22, where # represents a null node.%0A%0A Given a string of comma separated values, verify whether it is a correct preorder traversal serialization of a binary tree. Find an algorithm without reconstructing the tree.%0A%0A Each comma separated value in the string must be either an integer or a character '#' representing null pointer.%0A%0A You may assume that the input format is always valid, for example it could never contain two consecutive commas such as %221,,3%22.%0A%0A Example 1:%0A %229,3,4,#,#,1,#,#,2,#,6,#,#%22%0A Return true%0A%0A Example 2:%0A %221,#%22%0A Return false%0A%0A Example 3:%0A %229,#,#,1%22%0A Return false%0A%0A%0A */%0A
 publ

refactor 331