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

1. 题目描述

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

参考以下这颗二叉搜索树：

     5
    / \
   2   6
  / \
 1   3

2. 示例

示例 1：
输入: [1,6,3,2,5]
输出: false

示例 2：
输入: [1,3,2,6,5]
输出: true

提示：
数组长度 <= 1000

3. 解题

后序遍历时，遍历数组的结构为：左子数|右子树|根节点
且左子树中所有值都小于根节点，右子树中所有值都大于根节点，因此，我们首先需要解决的问题是如何定位 左子树和右子树。
可以想到，既然左子树中值都小于根节点，那么从根节点位置往前遍历，第一个小于根节点的值，就是左子树的最后一个值，这样就可以定位左右子树
再通过递归判定，可判断给定数组是否为某一个二叉查找树的后序遍历