LeetCode 331. 验证二叉树的前序序列化
原题链接
中等
class Solution {
private char[] charArray;
private int u = 0;
private boolean isBinaryTree(int root) {
if(root >= charArray.length) return false;
// 记录递归到哪里了,也就是左子树的前序遍历的最后一个节点位置
u = root;
if(charArray[root] == '#') return true;
// 当前数字可能是多位的
while(root < charArray.length && charArray[root] != ',') root ++;
boolean leftIsBrinaryTree = isBinaryTree(root + 1);
boolean rightIsBrinaryTree = isBinaryTree(u + 2);
return leftIsBrinaryTree && rightIsBrinaryTree;
}
public boolean isValidSerialization(String preorder) {
this.charArray = preorder.toCharArray();
return isBinaryTree(0) && u == charArray.length - 1;
}
}