输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。
//方案一:
public class Solution {
public boolean VerifySquenceOfBST(int [] sequence) {
int len=sequence.length-1;
if(len<0)
return false;
int i=0;
while(len>0){
while(sequence[i]<sequence[len])
i++;
while(sequence[i]>sequence[len])
i++;
if(i<len)
return false;
i=0;
len--;
}
return true;
}
}
//方案二
public class Solution {
public boolean VerifySquenceOfBST(int [] sequence) {
int len=sequence.length-1;
if(len<0)
return false;
return f(sequence,0,len);
}
public boolean f(int a[],int start,int end){
if(start==end)
return true;
int left=start;
while(a[left]<a[end]&&left<end)
left++;
int right=left;
while(a[right]>a[end]&&right<end)
right++;
if(right<end)
return false;
if(left==start||left==end)//只有左子树或者只有右子树
return f(a,start,end-1);
else //既有左子树又有右子树
return f(a,start,left-1)&&f(a,left,end-1);
}
}
//感觉似乎方案一更好理解,方案二思路上好像更简单些