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

Solution

public class Solution {
    public boolean isValidSerialization(String preorder) {
        String[] nodes = preorder.split(",");
        if(nodes.length == 1 && isNull(nodes[0])) return true; // root is a null

        Stack<Integer> stack = new Stack<Integer>();
        for(int i = 0; i < nodes.length; i++) {
            if(isNull(nodes[i])) {
                if(stack.isEmpty()) {
                    return false;
                } else {
                    while(stack.size() > 0 && stack.peek() == 1) stack.pop();
                    if(stack.size() == 0) {
                        return i == nodes.length - 1; // has to be the last one
                    } else {
                        stack.pop();
                        stack.push(1);
                    }
                }
            } else {
                stack.push(2);
            }

        }
        return stack.size() == 0;
    }

    public boolean isNull(String s) {
        if(s.length() == 1 && s.charAt(0) == '#') return true;
        else return false;
    }

}