该题目来源于牛客网《剑指offer》专题。

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

Go语言实现：

//BST结构：left<root<right，后序遍历顺序：left，right，root

//后序遍历序列S，最后一个元素是x，root为x

//去掉x的序列为T，T分成两段，前一段小于x，后一段大于x

func verifySquenceOfBST(s []int) bool {

   length := len(s)

   if length == 0 {

      return true

   }

   return isBST(s, 0, length-1)

}

func isBST(s []int, start, end int) bool {

   if start >= end {

      return true

   }

   x := s[end]

   i := start

   //左边小

   for i = start; i < end; i++ {

      if s[i] > x {

         break

      }

   }

   //右边大

   for j := i; j < end; j++ {

      if s[j] < x {

         return false

      }

   }

   //i开始大于，所以i-1；新的一轮，取走x，所以end-1

   return isBST(s, 0, i-1) && isBST(s, i, end-1)

}