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

/**我的思路稍微与大伙有所不同，我们知道二叉搜索树的中序遍历结果就是数组排序过后的结果，
所以这就相当于知道了中序和后序，中序肯定是正确的，后序的结果正不正确不确定，
我们先假设后序结果是正确的.
当中途推出毛病了，那么就不是正确了，
如何判断有毛病呢.
后序数组的最后一个元素一定是根，那么我们就按照这个根划分，
如果这个根元素在中序数组里面则假设是合法的，如果不在中序数组里面，则假设不合理，可直接得到答案
*/
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)//根节点不在中序数组里面，说明假设不成立，直接得到答案
            result=false;
        }
}