判断二叉搜索树的后序遍历
思路：二叉搜索树的特点，左子树的值都比根节点小，右子树的值都比根节点大，后序遍历不用讲了吧，那么后序遍历得到的序列最后一位为根节点，然后根据BST特点，从头开始遍历，寻找左子树与右子树的分界点，找到之后，先判断右子树是否满足，不满足直接返回，再依次递归分别判断左子树与右子树是否满足条件。
import java.util.*;
public class postOrderTraverse {
static Scanner in = new Scanner(System.in);
static boolean BST(int[] a,int s,int e) {
int i = s;
while(i<e-1&&a[i]<a[e-1])i++;//寻找左子树与右子树的分割点
int j = i;
while(j<e-1&&a[j]>a[e-1])j++;
if(j<e-1) return false;//如果右子树不满足，返回false
//分别递归搜索左子树与右子树是否满足条件
boolean left = true;
if(i>0) left = BST(a, 0, i);
boolean right = true;
if(j<e-1) right = BST(a, i+1, e);
return left&&right;
}
public static void main(String[] args) {
// int[] a = {2,6,5,9,11,10,8};
int[] a = {8,5,2,6,10,9,11};
System.out.println(BST(a,0,a.length));
}
}
