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