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

知识点：二叉搜索树是一个左子树的所有值都小于根节点，右子树的所有值都大于的根节点的特殊二叉树。

思路：主要是根据二叉搜索树的性质去处理。后序遍历的二叉树，其根节点在数组的最后面，根据二叉搜索树的性质，找出二叉树左右子树的分界线，然后查看右子树中有没有比根节点小的值，若存在则不是二叉搜索树。

时间：2021年8月5号

public class Solution {
  public boolean VerifySquenceOfBST(int [] sequence) {
      //实际上就是对二叉搜索树的后序遍历
      int len = sequence.length - 1;

      if (sequence == null || len < 0)
          return false;

      return helpVerify(sequence, 0, len);
  }

  public boolean helpVerify(int[] nums, int start, int end) {
      //递归边界
      if (start >= end)
          return true;

      int key = nums[end];
      int i = 0;

      for (i = start; i < end; i++) {
          //找到二叉树的左右子树的分界线，i
          //所以i应该是右子树的下标
          if (nums[i] > key) {
              break;
          }
//             System.out.println(i);//[4,6,7,5]
      }

      for (int j = i; j <= end; j++) {
          if (nums[j] < key)
              return false;
      }

      return helpVerify(nums, start, i-1) && helpVerify(nums, i, end-1);
  }
}