题解 | #二叉搜索树的后序遍历序列#

//首先我们知道二叉搜索树的中序遍历就是将数组排序，也就是说数组排序过后就是二叉搜索树的中序遍历结果
//所以我们先将数组排序，得到它的中序遍历结果，然后现在有了后序和中序，我们先假设他是后序遍历的结果
//等中途推出毛病了，证明他就不是二叉树的后序遍历。因为中序是确定的，并且后序的最后一个肯定是根
//我们就判断这个根是否在中序数组里面就可以了，如果不在说明就不是后序遍历的结果
import java.util.Arrays;
public class Solution {
    private boolean result=true;
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence.length==0)
            return false;
       int[] mid=new int[sequence.length];
        for(int i=0;i<sequence.length;i++){
            mid[i]=sequence[i];
        }
        Arrays.sort(mid);
        isHaving(mid,0,mid.length-1,sequence,0,sequence.length-1);
        return result;
    }
    private void isHaving(int[] mid,int midstart,int midend,int[] last,int laststart,int lastend){
            if(midstart>midend||laststart>lastend)
                return ;
        int temp=last[lastend];
        boolean flag=false;
        for(int i=midstart;i<=midend;i++){
            if(temp==mid[i]){
                flag=true;//说明后序的根在中序数组中，继续进行下一个节点的判断
                isHaving(mid,midstart,i-1,last,laststart,laststart+i-midstart-1);//判断左子树
                isHaving(mid,i+1,midend,last,laststart+i-midstart,lastend-1);//判断右子树
            }
        }
        if(!flag)//说明后序的根不在中序数组，结果直接就是FALSE了
            result=false;
        }
}