题解 | #二叉搜索树的后序遍历序列# 小白能看懂！

import java.util.*;
public class Solution {
    /*
  思路：由于题目给出的是二叉搜索树的后续校验。
        所以，我们应该充分的往二叉搜索树中的性质方面考虑，并且利用它的性质解题
        性质：对于任何一个根来说，根的左边全部小于根，根的右边全部大于根。并且后续数组中尾元素一定是根！
        所以！我们只需要找一个分界值，这个分界值可以用来区分根的左右子树。
        然后分别递归校验左右子树即可。（因为左右子树校验思路一样，所以可以递归）
        
        代码步骤就是：
            1）通过根节点，来找一个分界值，用来区分左右子树（当分界值找到后。那么对于分界值的左边所有元素就是当前根的左子树，分界值以及分界值的右边就是当前根的右子树。）
            2）提前校验右子树中是否全部元素大于根，只要有一个不是，提前终止程序！
            3）递归校验左子树。递归校验右子树！
        
        递归终止条件：当数组中为空就return true；
    */
    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;
    }
}