public class Solution {
public boolean isValidSerialization(String preorder) {
int i = traverse(preorder, 0);
return i >= preorder.length();
}
public static int traverse(String preorder, int i) {
if (i >= preorder.length()) return i;
if (i < 0) return i;
while (preorder.charAt(i) == ',') {
i++;
}
char root = preorder.charAt(i);
if (root == '#') return i + 1;
while (i < preorder.length() && preorder.charAt(i) != ',') {
i++;
}
int left = traverse(preorder, i);
if (left >= preorder.length()) return -i;
int right = traverse(preorder, left);
return right;
}
}
public boolean isValidSerialization(String preorder) {
String[] nodes = preorder.split(",");
int diff = 1;
for (String node: nodes) {
if (--diff < 0) return false;
if (!node.equals("#")) diff += 2;
}
return diff == 0;
}
public class Solution {
public boolean isValidSerialization(String preorder) {
Stack<String> stack = new Stack<>();
String[] strs = preorder.split(",");
for (int i = 0; i < strs.length; i++) {
while (strs[i].equals("#") && !stack.isEmpty() && stack.peek().equals("#")) {
stack.pop();
if (stack.isEmpty()) return false;
stack.pop();
}
stack.push(strs[i]);
}
return stack.size() == 1 && stack.peek().equals("#");
}
}