根据后序数组重建搜索二叉树

#判断当前序列是否是二叉搜索树后序遍历
#二叉搜索树的特点是左子树小于根，右子树大于根
#而后序遍历是左右根的顺序
#所以序列应该是从小到大的顺序
def isBST(nums, low, high) -> bool:
    #叶节点
    if low >= high:
        return True
    #根节点
    last = nums[high]
    i = 0
    #找到右子树入口
    for i in range(low, high):
        if nums[i] > last:
            break
    #在右子树中判断
    #右子树中的节点值应该是大于根节点值的
    for j in range(i + 1, high):
        #违反了规定
        #一定不是
        if nums[j] < last:
            return False
    #分别在两棵子树中递归进行判断
    return isBST(nums, low, i - 1) and isBST(nums, i, high - 1)

n = eval(input())
nums = list(map(int, input().split()))
rlt = isBST(nums, 0, len(nums) - 1)
if rlt:
    print('true')
else:
    print('false')

import java.util.*;

class Node {
    public int val;
    public Node right;
    public Node left;
    public Node (int data) {
        this.val = data;
    }
}

public class Main {
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        boolean res = testBST(arr);
        System.out.println(res);
    }
    
    public static boolean testBST(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 = start-1;
        int more = end;
        //找最后一个小于自己和大于自己的index
        for (int i = start; i < end; i++) {
            if (arr[end] > arr[i]) {
                less = i;
            }
            else {
                more = more == end ? i : more;
            }
        }
        //如果不满足左边小右边大，则直接返回false
        if (less != more - 1) {
            return false;
        }
        //如果列数组中所有数都比root小或都比root大，则检查子树
        if (less == start-1 || more == end)
            return isPost(arr, start, end-1);
        return isPost(arr, start, less) && isPost(arr, more, end-1);
    }
}

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
        int[] arr = new int[n];
        for(int i=0;i<n;i++){
            arr[i] = scanner.nextInt();
        }
        System.out.println(isPostOrder(arr, 0, n-1));
		
	}
	
	
	private static boolean isPostOrder(int arr[],int start,int end) {
		if(start >=end) return true;
		// 记录根节点的值，搜索二叉树的根节点必须满足左 <根<右
		int rootVal = arr[end];
		boolean flag = false;
		int mid = end;
        // 找到第一个比根节点大的值，且必须满足之后的节点也大于根节点
		// 记录第一个比根节点大的值的下标，此为左右数组划分的位置
		for(int i=start;i<end;i++) {
			if(!flag && arr[i]>rootVal) {
				mid = i;
				flag = true;
			}else if(flag && arr[i]<rootVal) {
				return false;
			}
		}
		
		return isPostOrder(arr, start, mid-1) && isPostOrder(arr, mid, end-1);
	}
}

#include<bits/stdc++.h>
using namespace std;
bool judge(int start,int end,vector<int>& v)
{
    if(start==end) return true;
    int i;
    // 找到第一个比根节点大的位置
    for(i=start;i<end;++i)
    {
        if(v[i]>v[end])
            break;
    }
    // 单支树
    if(i==start || i==end)
        return judge(start,end-1,v);
    // 否则，小于根值的结点在左侧，大于根的节点值须在右侧
    for(int j=i;j<end;++j)
    {
        if(v[j]<v[end])
            return false;
    }
    return judge(start,i-1,v) && judge(i,end-1,v);
}
int main()
{
    int n;
    cin>>n;
    vector<int>v(n);
    for(int i=0;i<n;++i)
    {
        cin>>v[i];
    }
    cout<<( judge(0,n-1,v) ? "true" : "false");
    return 0;
}

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
        int[] arr = new int[n];
        for(int i=0;i<n;i++){
            arr[i] = scanner.nextInt();
        }
        System.out.println(isPostOrder(arr, 0, n-1));
		
	}
	
	
	private static boolean isPostOrder(int arr[],int start,int end) {
		if(start >=end) return true;
		
		int rootVal = arr[end];
		boolean flag = false;
		int mid = end;
		for(int i=start;i<end;i++) {
			if(!flag && arr[i]>rootVal) {
				mid = i;
				flag = true;
			}else if(flag && arr[i]<rootVal) {
				return false;
			}
		}
		
		return isPostOrder(arr, start, mid-1) && isPostOrder(arr, mid, end-1);
	}
}