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

思路1

使用栈，每遇到有两个#连在一起的时候，就意味着有一个叶子节点检测完了，我们从栈里去掉这两个空节点和叶子节点，将这个叶子节点替换为#。
举个例子：
preorder = 1,2,3,#,#,#,#
Pass 1: stack = [1]
Pass 2: stack = [1,2]
Pass 3: stack = [1,2,3]
Pass 4: stack = [1,2,3,#]
Pass 5: stack = [1,2,3,#,#] -> stack = [1,2,#]
Pass 6: stack = [1,2,#,#] -> stack = [1,#]
Pass 7: stack = [1,#,#] -> stack = [#]
最后stack的样子应该是这样的：stack=[#]，否则就是错的。。。。

在这个过程中，有些情况直接就可以判断这个先序遍历是错的，不需要再向后遍历字符串了。

var isValidSerialization = function(preorder) {
    preorder = preorder.split(',');
    var num = preorder.length;
    var stack = [preorder[0]];
    for (var i = 1;i < num;i++) {
        if (stack.length===0)
            return false;
        if (preorder[i]!=='#') {
            stack.push(preorder[i]);
        } else {
            if (stack[stack.length-1]==='#') {
                stack.pop();
                if (stack.length===0)
                    return false;
                stack.pop();
                stack.push("#");
                while (stack.length>2&&stack[stack.length-1]==='#'&&stack[stack.length-2]==='#') {
                    stack.pop();
                    stack.pop();
                    if (stack.length===0)
                        return false;
                    stack.pop();
                    stack.push("#");
                }
            } else {
                stack.push("#");
            }
        }
    }
    if (stack.pop()!=='#')
        return false;
    if (stack.length!==0)
        return false;
    return true;
};

思路2

用图的理论来做这些。
一个根节点提供两个出度
一个非叶子节点提供一个入度两个出度
一个叶子节点提供一个入度
最后所有的出度和入度相减应该为0
我们设diff=出度-入度
然后每遍历一个节点，减掉一个入度，如果这个节点不是叶子节点我们再加上两个出度
由于根节点有一点特殊，比起其他非叶子节点，它不提供一个入度，所以我们初始化diff为1来抵消这一点。
由于是先序遍历，diff永远不可能小于0。

var isValidSerialization = function(preorder) {
    preorder = preorder.split(',');
    var diff = 1;
    for (var i = 0;i < preorder.length;i++) {
        diff--;
        if (diff<0)
            return false;
        if (preorder[i]!=='#')
            diff += 2;
    }
    return diff===0;
};

这个算法虽然简单，但是极大的可能需要遍历整个字符串才能得到结果。