ac

给定一个有 n 个不重复整数的数组 arr，判断 arr 是否可能是节点值类型为整数的搜索二叉树后序遍历的结果。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

class TreeNode{
    TreeNode left;
    TreeNode right;
    int val;

    public TreeNode(int val) {
        this.val = val;
        left = null;
        right = null;
    }
}

class Rs{
    boolean isBalance;
    int height;

    public Rs(boolean isBalance, int height) {
        this.isBalance = isBalance;
        this.height = height;
    }
}

public class Main {
    public static Scanner sc = new Scanner(System.in);

    public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

    public static long mod = (long) Math.pow(2, 29);

    public static void main(String[] args) throws Exception {
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        boolean b = isPost(arr, 0, n - 1);
        System.out.println(b ? "true" : "false");
    }

    static boolean isPost(int[] arr, int left, int right){
        if(left >= right){
            return true;
        }
        int midVal = arr[right];
        int index = left;
        while (index < right && arr[index] < midVal){
            index ++;
        }
        int leftEnd = index - 1;
        // 只有右，进一步判断下
        if(leftEnd < left){
            boolean flag = true;
            for(int i=left;i<right;i++){
                if(arr[i] < midVal){
                    flag = false;
                    break;
                }
            }
            if(!flag) {
                return false;
            }
        }
        // 左右都有
        if(leftEnd < right -1){
            boolean flag = true;
            for(int i=leftEnd+1;i<right;i++){
                if(arr[i] < midVal){
                    flag = false;
                    break;
                }
            }
            if(!flag) {
                return false;
            }
        }
        return isPost(arr, left, leftEnd) && isPost(arr, leftEnd+1 , right-1);
    }

}
/*
3
1 3 2

true
 */