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);
  }
}

```