难度中等656
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
参考以下这颗二叉搜索树：
5
/ \
2 6
/ \
1 3示例 1：
输入: [1,6,3,2,5]
输出: false示例 2：
输入: [1,3,2,6,5]
输出: true提示：
数组长度 <= 1000
解题思路：
这道题要是有给出树的根节点，那么我们只需要去后序遍历一遍树然后得到一个后序遍历序列与题目给的序列比较即可，但是难就难在题目只给出了后序遍历的序列而已！
这道题有多种解法，这里记录的是一种比较好理解但是不容易想到的解法！
其实大体思路和构建二叉树的思路是一样的！因为这道题给的条件是二叉搜索树，我们要利用左小右大的特点，在模拟构建的同时进行判断，如果不符合则进行剪枝！
而我们是不需要真的构建二叉树的，我们只需要模拟这个过程，从而节省了这部分的空间复杂度！
如果模拟构建完成之后，最终这个序列列表为空，说明是合法的BST。若构建结束后列表不为空，说明不是合法的BST。
因为是后序遍历，也就是遵循 左子树-》右子树-》根节点，所以我们构建的时候是从根节点开始，那么就要倒着去遍历这个序列，就变成了 根节点-》右子树-》左子树，这个是要注意的！
然后在遍历到当前节点的时候，判断一下当前节点的值，是否比左子树的最大节点值要大，是否比右子树的最小节点值要小，若都是的话则说明当前这个节点就是符合的，则我们将其从序列中 pop_back 掉，继续执行剩下的节点。若不符合，说明可能是从右子树过渡到了左子树，那么这个函数调用会一直回溯到原来的根节点后去调用左子树完成接下来的工作！（这是理解这个代码的一个难点，可以自己模拟一下过程）
要注意的是第一个节点进行判断也就是根节点判断的时候，我们给出的左子树的最大节点值要设为 INT_MIN，右子树的最小节点值要设为 INT_MAX，这样子才能保证根节点能继续往下走！
具体的步骤参考代码，可以用代码和例子模拟过程，这样子会更加熟悉这个方法！
class Solution
{
public:
void build(vector<int> &postorder, int lMax, int rMin)
{
// 若列表为空则直接return
if (postorder.empty())
return;
// 比较是否符合BST的规则，不符合的话直接return
int rootValue = postorder[postorder.size() - 1];
if (rootValue < lMax || rootValue > rMin)
return;
// 走到这说明符合规则，则将该节点去掉
postorder.pop_back();
// 注意postorder先走的是右子树，所以我们要将lMax变成rootValue作为新的左子树的最大节点
build(postorder, rootValue, rMin);
build(postorder, lMax, rootValue);
}
bool verifyPostorder(vector<int> &postorder)
{
build(postorder, INT_MIN, INT_MAX);
return postorder.empty(); // 返回序列是否为空的结果！
}
};