题意

给定一个数组，判断它是否可以是二叉搜索树的后序遍历序列

分析

法一：
二叉搜索树这个条件天然的告诉了我们这棵二叉搜索树的中序遍历序列，就是把这个数组排个序。
有了中序和后序遍历序列，就可以重建二叉树。
法二：
直接从这个序列判断是否为合法的后序遍历序列。
后序遍历序列的根节点就是最后一个元素，判断是否为合法的后序遍历，要看按照后序的规则是否为合法的二叉搜索树。尝试对最后一个元素之前的元素做划分，前一部分比最后一个元素小，后一部分比最后一个元素大，如果不存在这样的划分，那么返回 false，如果存在，那么再判断这两个子序列是否为合法的后序遍历序列。这样就将问题规模缩小了，可以递归求解。

class Solution {
public:
    bool verifySequenceOfBST(vector<int> sequence) {
        int len = sequence.size();
        if(len <= 1)return true;
        return isBST(sequence, 0, len-1);
    }

    bool isBST(vector<int>& seq, int l, int r){
        if(l == r)return true;

        int index = r - 1;
        while(index >= l && seq[index] > seq[r])index --;
        int tmp = index;
        while(tmp >= l){
            if(seq[tmp] > seq[r])return false;
            tmp --;
        }
        if(index < l)return isBST(seq, l, r-1);
        if(index == r-1)return isBST(seq, l, r-1);

        return isBST(seq, l, index) && isBST(seq, index+1, r-1);
    }
};