Verify Preorder Serialization of a Binary Tree

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

利用逗号隔开，没遍历到一个逗号，则前面的是树的一个节点，如果这个节点不是空节点(空节点表示为#)

在遍历到叶节点的时候，肯定有两个空节点(是叶节点的孩子)

//capacity表示当前容量，初始为1，表示有根节点
class Solution {
public:
    bool isValidSerialization(string preorder) {
        if (preorder.empty()) return false;
        preorder+=',';
        int sz=preorder.size(),idx=0;
        int capacity=1;
        for (idx=0;idx<sz;idx++){
            if (preorder[idx]!=',') continue;
            capacity--;


            if (capacity<0) return false;
            //节点，表示可以有两个孩子
            if (preorder[idx-1]!='#') capacity+=2;
        }
        return capacity == 0;
    }
};