题目描述
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
方法1：递归统计个数
思路：二叉搜索树的后续遍历对应的根结点为该数组的最后一个元素，记为temp。满足二叉搜索树条件：左子树所有节点值<temp，而右子树所有节点值>temp。我们用list1和list2分别存左子树和右子树节点，递归左右子树。满足二叉搜索树条件：list1.size()+list2.size()=数组长度减1.否则则返回false.
【运行时间：14ms 占用内存：8280k】
import java.util.*;
public class Solution {
public boolean VerifySquenceOfBST(int [] sequence) {
ArrayList<Integer> list1=new ArrayList<Integer>();
ArrayList<Integer> list2=new ArrayList<Integer>();
if(sequence==null||sequence.length==0) return false;
if(sequence.length==1) return true;
int temp=sequence[sequence.length-1];
Boolean flag=false;//用flag标记是否访问过
int size=sequence.length-1;
for(int i=0;i<size;i++){
if(sequence[i]<temp&&(!flag)){
list1.add(sequence[i]);
}else if(sequence[i]>temp){
list2.add(sequence[i]);
flag=true;
}
}
//判断元素数目是否一样
if(size!=(list1.size()+list2.size())){
return false;
}
//左子树
int left[]=new int[list1.size()];
for(int i=0;i<list1.size();i++){
left[i]=list1.get(i);
}
//右子树
int right[]=new int[list2.size()];
for(int i=0;i<list2.size();i++){
right[i]=list2.get(i);
}
VerifySquenceOfBST(left);//递归左子树
VerifySquenceOfBST(right);//递归右子树
return true;
}
}
方法2：递归
参考牛客网网友回答，思路和我这差不多，但是比我写的简洁
public class Solution {
public boolean VerifySquenceOfBST(int [] sequence) {
if(sequence.length==0) return false;
return isBST(sequence,0,sequence.length-1);
}
public boolean isBST(int []sequence,int start,int end){
if(start>=end) return true;
//i为全局变量，记录第一个大于根结点的元素
int i=start;
for(;i<end;i++){
if(sequence[i]>sequence[end]) break;
}
//右子树判断
for(int j=i;j<end;j++){
//如果右子树中出现比根结点小的，返回false
if(sequence[j]<sequence[end]) return false;
}
return isBST(sequence,start,i-1)&&isBST(sequence,i,end-1);
}
}
方法3：非递归的解法
if(sequence==null||sequence.length==0) return false;
int len=sequence.length;
int i=0;
while(len!=0){
len--;
while((i<=len)&&(sequence[i++]<sequence[len]));
while((i<=len)&&(sequence[i++]>sequence[len]));
if(i<len)
return false;
i=0;
}
return true;
