题目链接：https://leetcode.com/problems/verify-preorder-serialization-of-a-binary-tree/
题目：
#.
_9_ / \ 3 2 / \ / \ 4 1 # 6 / \ / \ / \ # # # # # #
"9,3,4,#,#,1,#,#,2,#,6,#,#", where #
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.
'#' representing null"1,,3".Example 1:
"9,3,4,#,#,1,#,#,2,#,6,#,#"
Return trueExample 2:
"1,#"
Return falseExample 3:
"9,#,#,1"
Return false
思路：
两个＃可以退一个栈，最后如果栈只剩一个＃则true否则false
算法：
public boolean isValidSerialization(String preorder) {
Stack<String> stack = new Stack<String>();
String ps[] = preorder.split(",");
for (int i = 0; i < ps.length; i++) {
stack.push(ps[i]);
while (!stack.isEmpty() && stack.peek().equals("#") && stack.size() >= 3
&& stack.get(stack.size() - 2).equals("#") && !stack.get(stack.size() - 3).equals("#")) {
stack.pop();
stack.pop();
stack.pop();
stack.push("#");
}
}
return stack.size() == 1 && stack.peek().equals("#");
}