二叉搜索树的后序遍历序列

public class Solution {
    public boolean VerifySquenceOf(int [] sequence,int start,int end)
    {
        if(start>=end)
        return true;

        int root=sequence[end];
        int i=start;
        while(i<=end&&sequence[i]<root)
        {
            i++;
        }
        for(int j=i;j<end;j++)
        {
            if(sequence[j]<root)
            return false;
        }

        return VerifySquenceOf(sequence,start,i-1) && VerifySquenceOf(sequence,i,end-1);

    }
    public boolean VerifySquenceOfBST(int [] sequence) 
    {
        if(sequence==null || sequence.length==0)
        return false;
        return VerifySquenceOf(sequence,0,sequence.length-1);
        
    }
}

public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if (sequence.length == 0) {
            return false;
        }
        return VerifySquenceOfBSTCore(sequence, 0, sequence.length - 1);
    }
    private boolean VerifySquenceOfBSTCore(int[] sequence, int start, int end) {
        //在不断查找过程中，区域不断缩小，为空时，证明之前的所有范围都满足检测条件
        // 也就是是一个BST
        if (start >= end) {
            return true;
        }
        //拿到root节点的值
        int root = sequence[end];
        //先遍历左半部分，也就是整体都要比root小，拿到左子树序列
        int i = start;
        while (i < end && sequence[i] < root) {
            i++;
        }
        //在检测右子树是否符合大于root的条件,要从i开始，也就是右半部分的开始
        for (int j = i; j < end; j++) {
            if (sequence[j] < root){
                return false;
            }
        }
        //走到这里，就说明，当前序列满足需求。但并不代表题目被解决了，还要在检测left和right各自是否也满 足
        return VerifySquenceOfBSTCore(sequence,start,i-1) && VerifySquenceOfBSTCore(sequence,i,end-1);
    }
}

import java.util.*;
public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence.length==0) return false;
        return jiaoyan(sequence);
    }
     public boolean jiaoyan(int[] sequence){
        // 递归终止条件:数组为空停止。
        if(sequence.length<1) return true;
         
        int index=0;
        // 获取根节点
        int root = sequence[sequence.length-1];
         // 先找一个左右子树的分界值
        while(index<sequence.length-1){
            if(sequence[index]>root){
                break;
            }
            index++;
        }
        // 程序能执行到此处，说明index 左边的元素全是左子树， index 右边的元素全是右子树
        // 先校验右子树中是否全部元素大于根。
        int temp = index;
        while(temp<sequence.length-1){
            if(sequence[temp]<root){
                return false;
            }
            temp++;
        }
        // 递归校验左子树
        boolean left = jiaoyan(Arrays.copyOfRange(sequence,0,index));
        // 递归校验右子树
        boolean right = jiaoyan(Arrays.copyOfRange(sequence,index,sequence.length-1));
        return left && right;
    }
}

    private boolean verify(int[] sequence, int first, int last) {
        // 递归终止条件
        if (last - first <= 1) {
            return true;
        }
        // 后序遍历:“左子树-右子树-根节点”，所以rootVal是根值
        int rootVal = sequence[last], cutIndex = first;
        // 左子树均小于根值
        while (cutIndex < last && sequence[cutIndex] < rootVal) {
            //(由于你不清楚数组哪一部分是左子树，就先把小于根值的都划归左子树，这样剩下的都成了右子树，咱们就判断右子树是否合规)
            cutIndex++;
        }
        // 右子树均大于根值
        for (int i =cutIndex; i < last; i++) {
            if (sequence[i] < rootVal) {
                return false;
            }
        }
        // 递归
        return verify(sequence, first, cutIndex - 1) && verify(sequence, cutIndex, last - 1);
    }

    public boolean verifySequenceOfBST(int[] sequence) {
        // 判空
        if (sequence == null || sequence.length == 0) {
            return false;
        }
        // 二叉排序树BST：左 < 中 < 右
        return verify(sequence, 0, sequence.length - 1);
    }

	public static boolean VerifySquenceOfBST(int [] sequence) {
		if (sequence == null || sequence.length == 0 ) {
			return false;
		}
		return VerifySquenceOfBST(sequence, 0, sequence.length -1 );

	}

	private static boolean VerifySquenceOfBST(int[] sequence, int start, int end) {
		if (start > end) {
			return true;
		}
		//最后一个是root节点
		int root = sequence[end];

		//从左向右，找到小于root节点的，认为是左子树，其他的认为是右子树，都要>root 节点
		int left = start;
		while (left < end && sequence[left] < root) {
			left++;
		}

		//右子树都要> root,否则返回false
		int right = left +1;
		while (right < end) {
			if (sequence[right++] < root) {
				return false;
			}
		}
		return VerifySquenceOfBST(sequence, start, left -1) && VerifySquenceOfBST(sequence,left, end -1);
	}

public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence.length==0) return false;
       return dfs(sequence,0,sequence.length-1);
    }
    public boolean dfs(int [] sequence,int start,int end){
        if(start>=end) return true;//表示为1个数字
        int midval=sequence[end];
        int i=start;
        while(i<end&&sequence[i]<midval){
            i++;
        }
        boolean leftrst=true;
        if(i!=start){//左子树不为空
            leftrst=dfs(sequence,start,i-1);
        }
         for(int p=i;p<end;p++){//右子树存在大于mid的值,不为后续遍历 返回false
            if(sequence[p]<midval){
                //rightrst=false;
                return false;
            }
          }
        boolean rightrst=dfs(sequence,i,end-1);
        return leftrst&&rightrst;

    }
}

public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence.length == 0)
            return false;
        return verify(sequence, 0, sequence.length-1);
    }
    
    //利用递归循环看左子树和右子树是否所有的值都符合要求
    public boolean verify(int[] seq, int l, int r) {
        //如果左右重合，说明只剩一个数了，说明之前的数都符合BST规则
        if (l >= r)
            return true;
        //找根
        int root = seq[r];
        //找出左右子树分界点
        int i = r-1;
        while (i >= l) {
            if(seq[i] < root)
                break;
            i--;
        }
        int j = i+1;
        int index = i;
        //循环看左右子树是否符合规则
        while(i >= l) {
            if (seq[i--] > root)
                return false;
        }
        while(j < r) {
            if (seq[j++] < root)
                return false;
        }
        //递归检查其余的数是否符合规则
        return verify(seq, l, index) && verify(seq, index+1, r-1);
    }
}

public class Solution {
    //左子树都应该小于根节点的值，按照此规律先找到左子树的最后一个节点
    //后面是右子树的值，应该都大于根节点的值
    //递归
    public boolean VerifySquenceOfBST(int [] sequence) {
        int len = sequence.length;
        if(len == 0) return false; //该题约定空树不是BST

        return help(sequence, 0, len - 1);
    }
    public boolean help(int [] sequence, int start, int end) {
        if(start >= end) return true;

        int root = sequence[end];
        int index = -1;
        //退出循环时，index指向左子树的最后一个节点
        for(int i = 0; i < end; i++) {
            if(sequence[i] < root) { //无重复的元素
                index++;
            }
        }
        //if(index == -1) 也可能没有左子树，不过到下一次递归函数中会处理

        for(int i = index + 1; i < end; i++) {
            if(sequence[i] < root) {
                return false;
            }
        }

        return help(sequence, start, index) &&
            help(sequence, index + 1, end - 1);
    }
}

public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence.length==0){
            return false;
        }
        
        return isbst(0,sequence.length-1,sequence);
        
    }
    public boolean isbst(int left,int right,int [] sequence){
        
        if(right<=left){
            //默认前面的正常搜索二叉树，
            //不能再进一步判断，返回true
            return true;
        }
        int lastright=right;//标记右边一段的下标
        int lastleft=left;//记左边一段的末下标
        int index=left;
        //遍历一次判断这次的数组是否符合
        while(index<right){
            if(sequence[index]<sequence[right]){
                //这里插入一个判断，只用一次遍历即可结束
                
                lastleft=index; //左边一段的末下标
                
                //用lastright和lastleft判断,
                //即在右边一段找到一个比根结点小的
                //因为右边一段的下标肯定比左边一段的大
                //左边一段遍历完了也即不可能再出现比根结点小的
                //如果出现，则返回失败
                if(lastleft>lastright){
                    return false;
                }
                index++;
            }
            if(sequence[index]>sequence[right]){
                //标记右边一段的下标
                lastright=index;
                index++;
            }
        }
        return  isbst(left,lastleft,sequence) &&
            isbst(lastleft+1,right-1,sequence);
    }
}