这个用了图的入度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
