题解 | #根据后序数组重建搜索二叉树#

import java.io.*;
import java.util.*;
public class Main {

    //判断一个数组arr是否为搜索二叉树的后序遍历
    /*后序遍历      左 右 根
    搜索二叉树：左子树的节点值均比根小，右子树的节点值均比根大
    递归
    * */
    public static boolean isPostArray(int[]arr){
        if(arr==null||arr.length==0){
            return false;
        }
        return isPost(arr,0,arr.length-1);
    }

    public static boolean isPost(int[]arr,int start,int end){
        if(start==end){
            return true;
        }
        int less=-1;    //左子树最右边
        int more=end;   //右子树最左边

        for(int i=start;i<end;i++){
            if(arr[i]<arr[end]){
                less=i;
            }else {
                //more=end说明还未开始确定右子树边界
                more= more==end?i:more;
            }
        }

        //只有右子树 或者 只有左子树
        if(less==-1||more==end){
            return isPost(arr,start,end-1);
        }
        //边界对不上
        if(less!=more-1){
            return false;
        }

        return isPost(arr,start,less)&&isPost(arr,more,end-1);

    }

    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        int[] arr=new int[n];
        for (int i = 0; i <n ; i++) {
            arr[i]=in.nextInt();
        }

        boolean result=isPostArray(arr);
        System.out.println(result);

    }
}