331. Verify Preorder Serialization of a Binary Tree

这个用了图的入度indegree和出度outdegree。其实用的是一个性质，full binary tree 的nonleaves == leaves + 1.
比如1(-1+2)(-1)(-1+2)(-1)(-1) == 0 。

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

}

引用另一种写法：

If we treat null's as leaves, then the binary tree will always be full. A full binary tree has a good property that # of leaves = # of nonleaves + 1. Since we are given a pre-order serialization, we just need to find the shortest prefix of the serialization sequence satisfying the property above. If such prefix does not exist, then the serialization is definitely invalid; otherwise, the serialization is valid if and only if the prefix is the entire sequence.

// Java Code
public boolean isValidSerialization(String preorder) {
    int nonleaves = 0, leaves = 0, i = 0;
    String[] nodes = preorder.split(",");
    for (i=0; i<nodes.length && nonleaves + 1 != leaves; i++)
        if (nodes[i].equals("#")) leaves++;
        else nonleaves++;
    return nonleaves + 1 == leaves && i == nodes.length;
}

ref:
https://discuss.leetcode.com/topic/35976/7-lines-easy-java-solution