Verify Preorder Serialization of

题目来源
判断一棵树的前序遍历结果是否合法。
没想出来怎么做，看了答案，解法一是利用栈，总的思想其实就是将两个#和一个数值替换成一个#，到最后替换成只剩一个#。

class Solution {
public:
    bool isValidSerialization(string preorder) {
        int n = preorder.size();
        if (n == 0)
            return false;
        stack<char> s;
        for (int i=0; i<n; i++) {
            if (preorder[i] == ',')
                continue;
            while (preorder[i] == '#' && !s.empty() && s.top() == '#') {
                s.pop();
                if (s.empty())
                    return false;
                s.pop();
            }
            while (preorder[i] <= '9' && preorder[i] >= '0' && i+1 < n && preorder[i+1] <= '9' && preorder[i+1] >= '0')
                i++;
            s.push(preorder[i]);
        }
        if (s.size() == 1 && s.top() == '#')
            return true;
        return false;
    }
};

还有另一个方法用入度=出度来实现。
diff = outdegree - indegree

class Solution {
public:
    bool isValidSerialization(string preorder) {
        int n = preorder.size();
        if (n == 0)
            return false;
        int dif = 1;
        for (int i=0; i<n; i++) {
            if (preorder[i] == ',')
                continue;
            if (--dif < 0)
                return false;
            if (preorder[i] != '#') {
                dif += 2;
                while (i < n && preorder[i] <= '9' && preorder[i] >= '0')
                    i++;
                i--;
            }
        }
        return dif == 0;
    }
};