package question;

import java.util.Stack;

/**
 * @author Roderland
 * @since 1.0
 */
public class Question331 {
 public boolean isValidSerialization(String preorder) {
 String[] split = preorder.split(",");
 Stack<String> stack = new Stack<>();
 for (String s : split) {
 if (s.equals("#")) {
 while (!stack.isEmpty() && stack.peek().equals("#")) {
 stack.pop();
 if (stack.isEmpty()) return false;
 else stack.pop();
 }
 }
 stack.push(s);
 }
 return stack.isEmpty() | (stack.size()==1&stack.peek().equals("#"));
 }
 public boolean isValidSerialization2(String preorder) {
 String[] split = preorder.split(",");
 Stack<Entity> stack = new Stack<>();
 for (String s : split) {
 if (stack.isEmpty() && s!=split[0]) return false;
 if (s.equals("#")) {
 if (!stack.isEmpty()) stack.peek().count--;
 } else {
 stack.push(new Entity(Integer.parseInt(s)));
 }
 while (!stack.isEmpty() && stack.peek().count<=0) {
 stack.pop();
 if (!stack.isEmpty()) stack.peek().count--;
 }
 }
 return stack.isEmpty();
 }

 static class Entity {
 int value;
 int count;

 public Entity(int value) {
 this.value = value;
 this.count = 2;
 }
 }
}