输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
二叉搜索树：根节点的值大于左节点的值，小于右节点的值；
后序遍历：按照左右根节点的顺序遍历二叉树；
/*首先，二叉搜索树，左子树值小于根节点，有子树值大于根节点 * 然后后序遍历是左右根的顺序----递归*/ public class 二叉搜索树的后序遍历序列 { public static void main(String[] args) { // TODO Auto-generated method stub } public boolean VerifySquenceOfBST(int [] sequence) { if (sequence.length==0) { return false; } return judge(sequence,0,sequence.length-1); } private boolean judge(int[] sequence, int start, int end) { // TODO Auto-generated method stub if (start>=end) { return true;//结束条件， } int i = start; for (; i < end; i++) { if (sequence[i]>sequence[end]) { break; } } int j = i; for (; j < end; j++) { if (sequence[j]<sequence[end]) { break; } } if (j==end) { return judge(sequence, start, i-1)&&judge(sequence, j, end-1); }else { return false; } } }
