题目描述

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

https://www.nowcoder.com/practice/a861533d45854474ac791d90e447bafd

解题想法

分治递归思想：序列最后一个元素是根节点，而二叉搜索树的根节点左边的序列值比根小，右边的比根大。

根据这个特性，将序列分为两半，左边序列的值比根节点小，右边序列的值比根节点大。如果序列出现不满足上述要求的，说明不是后序遍历序列。

代码实现

  1. public class Solution {
  2.     public boolean VerifySquenceOfBST(int [] sequence) {
  3.         // 异常条件
  4.         if (sequence == null || sequence.length == 0){
  5.             return false;
  6.         }
  7.         return func(sequence,0,sequence.length-1);
  8.     }
  10.     public boolean func(int [] a,int start,int end){
  11.         // 递归弹出条件
  12.         if (start >= end){
  13.             return true;
  14.         }
  15.         int i = start;
  16.         // 先找到序列的分界点
  17.            for ( ; i<end; i++){
  18.             if (a[i] > a[end]){
  19.                 break;
  20.             }
  21.         }
  22.         // 分界点右边的序列应该比根节点大，否则返回false
  23.         for (int j = i;j<end;j++){
  24.             if (a[j] < a[end]){
  25.                 return false;
  26.             }
  27.         }
  28.         // 
  29.         return func(a,start,i-1) && func(a,i+1,end);
  30.     }
  31. }