LeetCode 331. Verify Preorder Serialization of a Binary Tree

如家网络实在太卡了，不过还好没有人劫@!$#@W…
稍微说一下思路把，这个问题就是判断某一层上的节点它的孩子会不会“溢出”，或者第一层的节点有没有完全闭合。我用一个栈来保存每一层的孩子数目（包括null）：

• 当碰到数字的时候，压一层计数为0的栈，表示新开了一层并且这一层的孩子数为0
• 当碰到#号时，说明多了一个空孩子，当前栈顶的计数+1，并且判断当前栈顶的计数是否>=2了，如果是的话，那说明这一层已经满了，那就退栈，然后再继续给新栈顶计数+1，继续判断是否满….如此往复

由于有了#表示空节点所以层级变得明确，举个例子：一个叶节点读入两个#，当前层的计数等于2后就退栈，并且给父亲层的计数器+1（表示下一层已经结束了，父亲多了一个左/右孩子）。
代码（好久没有纯手打一遍AC了）

class Solution {
public:
    bool isValidSerialization(string preorder) {
        int size = preorder.size();
        stack<int> working;
        int i = 0;
        while(i < size){
            int end = preorder.find(',', i);
            if(end == string::npos)
                end = size;
            if(preorder[i] != '#'){
                //number
                working.push(0);
            } else {
                //'#'
                if(i == 0){
                    //The null root?!
                    if(size > 1) return false;
                    else return true;
                }
                working.top() += 1;
                while(working.size()>1 && working.top() >= 2){
                    working.pop();
                    working.top() += 1;
                }
            }
            if(working.size() == 1 && working.top() > 2)
                return false;
            i = end+1;
        }
        return (working.size()==1) && (working.top()==2);
    }
};

BTW,苏州的交通状况和路面比杭州好多了。