剑指offer-二叉搜索树的后序遍历

题目描述：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

思路：二叉搜索树特点，左子树的值小于头结点，右子树的值都大于头结点，后序遍历先左后右再头，因此末尾的总是头结点，递归进行判断

ac代码：

 1 public class Solution {
 2     public boolean VerifySquenceOfBST(int [] sequence) {
 3         if(sequence.length==0)
 4             return false;
 5         return isRight(sequence,0,sequence.length-1);
 6     }
 7     boolean isRight(int []s,int l,int r){
 8         if(l>=r)
 9             return true;
10         else {
11             int x=s[r];
12             int k=r;
13             for(int i=l;i<r;i++){
14                 if(s[i]>=x){
15                     k=i;
16                     break;
17                 }
18             }
19             boolean flag=true;
20             for(int i=k;i<=r;i++){
21                 if(s[i]<x){
22                     return false;
23                 }
24             }
25             return isRight(s,l,k-1)&&isRight(s,k,r-1);
26         }
27     }
28 }