原题链接在这里：https://leetcode.com/problems/verify-preorder-serialization-of-a-binary-tree/
题目：
One way to serialize a binary tree is to use pre-order traversal. When we encounter a non-null node, we record the node's value. If it is a null node, we record using a sentinel value such as #.
_9_
/ \
3 2
/ \ / \
4 1 # 6
/ \ / \ / \
# # # # # #
For example, the above binary tree can be serialized to the string "9,3,4,#,#,1,#,#,2,#,6,#,#", where # represents a null node.
Given a string of comma separated values, verify whether it is a correct preorder traversal serialization of a binary tree. Find an algorithm without reconstructing the tree.
Each comma separated value in the string must be either an integer or a character '#' representing null pointer.
You may assume that the input format is always valid, for example it could never contain two consecutive commas such as "1,,3".
Example 1:"9,3,4,#,#,1,#,#,2,#,6,#,#"
Return true
Example 2:"1,#"
Return false
Example 3:"9,#,#,1"
Return false
题解：
类似Serialize and Deserialize Binary Tree.
Method 1计算indegree和outdegree是否相加为0, 没遇到一个string, 就是遇到了一个节点, indegree++. root没有indegree, 但会算一遍outdegree, 为了补偿root. inDegree初始化为-1.
每当遇到一个非叶子节点, 就说明它必须有两个孩子. 就是有两个outDegree, 对应的inDegree就减掉2.
最后看inDegree是否为0.
Time Complexity: O(n). Space: O(n).
Method 2 利用stack来表示层级. 两种情况，一是遇到数字, push into stack.
一是#, 看栈顶是不是#, 若是，就一直pop, 每次pop不来两个, 直到不再是#,最后把当前的#再压入stack; 若不是#就 push into stack.
举例
_1_
/ \
3 2
/ \ / \
# # # #
压栈1, 压栈3, 压栈3的左侧叶子节点#. 当遇到3的右侧叶子节点时, pop出来两个, stack顶部变成1, 再把当前叶子节点压入stack中，stack现在有1, #.
就相当于
_1_
/ \
# 2
/ \
# #
以此类推，看最后stack的size是不是1, 并且唯一的保留就是#.
Time Complexity: O(n). Space: O(n). String array 大小 O(n), stack 大小O(logn).
AC Java:
public class Solution {
public boolean isValidSerialization(String preorder) {
if(preorder == null || preorder.length() == 0){
return true;
}
//Method 1, 算indegree 和 outdegree是否相加为0
String [] strArr = preorder.split(",");
int inDegree = -1; //根节点没有indegree, 但下面又算了一遍outdegree, 为了补偿初始inDegree 为-1
for(String str : strArr){
inDegree++; //没遇到一个str, 说明有一个node, 那么久有一个indegree
if(inDegree > 0){
return false;
}
if(!str.equals("#")){ //但凡非叶子节点，都有two children, outdegree就会多两个, 对比indegree就少两个.
inDegree-=2;
}
}
return inDegree == 0;
/*
//Method 2, 利用stack
Stack<String> stk = new Stack<String>();
String [] strArr = preorder.split(",");
for(String str : strArr){
//若此时stack顶是#, 说明该返回上一层, pop两次, 若顶部又是#, 说明再返回一层, 又pop两次
while(str.equals("#") && !stk.isEmpty() && stk.peek().equals("#")){
stk.pop();
if(stk.isEmpty()){ //pop了一个#, stack就空了, 说明没有parent节点, return false
return false;
}
stk.pop(); //一次pop出来两个
}
stk.push(str); //不论当前的str是什么，最后都压入stack中
}
return stk.size() == 1 && stk.peek().equals("#");
*/
}
}