public boolean isValidSerialization(String preorder) {
String[] strs = preorder.split(",");
int degree = 1; // root has no indegree, for compensate init with 1
for (String str: strs) {
degree++; // all nodes have 1 indegree (root compensated)
if (degree > 0) { // total degree should never exceeds 0
return false;
}
if (!str.equals("#")) {// only nonleaf node has 2 outdegree
degree = 2;
}
}
return degree == 0;
}
JAVA, Counting Indegree and Outdegree, SIMPLE & CLEAR!


@JosephTao Since this is a preorder serialization, degrees are calculated in a topdown fashion, and, tree is a structure that each node has only one indegree and at most two outdegree. Positive degree means there are more indegree than outdegree, which violates the definition.

If Input is [2 # 1 # #], it is invalid, but this solution would return true, right?
2 / \ # # / \ 1 #
Here is what happens at each stage. degree starts at 1
loop 1: str="2" > degree = (1+1)2 = 2
loop 2: str="#" > degree = (2+1) = 1
loop 3: str="1" > degree = (1+1)2 = 2
loop 4: str="#" > degree = (2+1) = 1
loop 5: str="#" > degree = (1+1) = 0
return true

