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

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

输入：
[4,8,6,12,16,14,10]
返回值：
true

2.思路

• 此题主要为搜索二叉树的后序遍历，首先搜索二叉树的左子树一定小于根节点，右子树一定大于根节点。
• 其次，后序遍历主要为先遍历左叶子节点=>右叶子节点=>根节点！！！
• 如此一来，正常的后序遍历顺序为：最后一个数为根节点(array[length-1]=root)，数组的前半部分为左子树，后半部分为右子树(扣除root)，所以关键在于找出前后两部分的分界线，那么就是value>root的那个位置了！
  方法：采用递归，当然有大牛更新奇的操作，不过实在看的头大，这里就不复现了。
  时间复杂度：递归方法在每一层的遍历开销是O(n)，而对于二叉树而言，递归的层数平均是O(logn)，因此，递归方法的最终复杂度是O(nlogn)
  代码如下：

  public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        //判空
        if(sequence.length==0){
            return false;
        }
        return judge(sequence,0,sequence.length-1);
    }
    //判断函数
    public boolean judge(int[] arr,int start,int end){
        //如果首尾相等，则说明已经遍历完了，且满足条件
        if(start>=end){
            return true;
        }
        //!!!!!此处刚开始赋值start不行，经过编译调整为end通过，求有缘人评论解答！！！谢谢
        int flag=end;
        //找到树中第一个大于根节点的位置并给flag
        for(int i=start;i<end;i++){
            if(arr[i]>arr[end]){
                  flag=i;
                  break;
            }
        }
        //遍历后面的，如果存在小于根节点的就返回false
        for(int j=flag;j<end;j++){
            if(arr[j]<arr[end]){
                return false;
            }
        }
        //递归，将左右子树再进行判断
        return judge(arr,start,flag-1)&&judge(arr,flag,end-1);
    }
  }
  

```