题目描述
判定二叉树前序序列是否合法
算法
时间复杂度O(n)
性质:二叉树边数=结点数+1
所以直接以“还剩多少空边可以存放节点”来模拟遍历
因为1 <= preorder.length
初始设置base=1代表至少有一个空位可以放节点(或者代表性质里面的“结点数+1”)
之后遍历先序序列:
1. 空节点——消耗一个空边,如果base==0,则返回false。进而base–
2. 其他节点——消耗一个空边,如果base==0,则返回false。获得两个空边,所以直接base++
3. 如果最终base==0,则返回true
C++代码
class Solution {
public:
bool isValidSerialization(string preorder) {
int base=1;
for(int i=0;i<preorder.size();i++)
if(preorder[i]=='#'){
if(base<=0)
return false;
i++;
base--;
}else{
if(base<=0)
return false;
while(i<preorder.size()&&preorder[i]!=',') i++;
base++;
}
return base==0;
}
};