23、二叉搜索树的后序遍历序列

一、题目

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

二、解法

 1 public class Solution {
 2 //非递归  
 3     //非递归也是一个基于递归的思想：
 4     //左子树一定比右子树小，因此去掉根后，数字分为left，right两部分，right部分的
 5     //最后一个数字是右子树的根他也比左子树所有值大，因此我们可以每次只看有子树是否符合条件
 6     //即可，即使到达了左子树左子树也可以看出由左右子树组成的树还想右子树那样处理 
 7     //对于左子树回到了原问题，对于右子树，左子树的所有值都比右子树的根小可以暂时把他看出右子树的左子树
 8     //只需看看右子树的右子树是否符合要求即可
 9     public boolean judge(int[] a, int start, int root){
10         if(start >= root)
11             return true;
12         int i = root-1;
13         //从后面开始找
14         while(i>=start && a[i] > a[root])
15             i--;//循环结束的条件是找到比根小的结点位置
16         //然后从前面开始判断，从start到i应该比根小
17         for(int j= start; j <= i; j++)
18             if(a[j] > a[root])
19                 return false;
20         //然后递归判断
21         return judge(a,start,i)&&judge(a,i+1,root-1);
22     }
23     public boolean VerifySquenceOfBST(int[] sequence) {
24         if(sequence.length == 0)
25             return false;
26         if(sequence.length == 1)
27             return true;
28         return judge(sequence,0,sequence.length-1);
29     }
30      
31 }