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

Thinking:

Accroding to the correct answer given, we can find the pattern. We should start from # and use stack to store it. When get two #, we should get another element from the string.

Solution:

public boolean isValidSerialization(String preorder) {
    String[] strlist = preorder.split(",");
    Stack<String> stack = new Stack<String>();
    Stack<String> tempstack = new Stack<String>();

    for (String s: strlist) {
        stack.push(s);
    }
    while (!stack.isEmpty()) {
        while (!stack.isEmpty() && stack.peek().equals("#")){
            tempstack.push(stack.pop());
        }
        if (tempstack.size() < 2)
            break;
        while (tempstack.size() >= 2 && !stack.isEmpty() && !stack.peek().equals("#")){
            tempstack.pop();
            tempstack.pop();
            if (!stack.isEmpty() && !stack.peek().equals("#")){
                stack.pop();
                tempstack.push("#");
            }
        }
    }

    if (tempstack.size() == 1 && stack.isEmpty())
        return true;
    else
        return false;
}

There is another simpler solution:

public boolean isValidSerialization(String preorder) {
    String[] p = preorder.split(",");
    int idx = 0; // stack
    for (int i = 0; i < p.length; i++) {
    if (p[i].equals("#")) {
        idx--;
    } else {
        if (idx < 0) { // check
          return false;
        }
        p[idx++] = p[i];
      }
    }
    return idx == -1; // check
  }

Reference: https://leetcode.com/discuss/83903/share-my-java-solution

And another much simplier solution which caculate the indegree and outdegree:

public boolean isValidSerialization2(String preorder) {
    String[] nodes = preorder.split(",");
    int diff = 1;
    for (String node: nodes) {
        if (--diff < 0) return false;
        if (!node.equals("#")) diff += 2;
    }
    return diff == 0;
}

Reference: https://www.hrwhisper.me/leetcode-algorithm-solution/