输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回 true ,否则返回 false 。假设输入的数组的任意两个数字都互不相同。
数据范围： 节点数量 0≤n≤10000≤n≤1000 ，节点上的值满足 1≤val≤1051≤val≤105 ，保证节点上的值各不相同 要求：空间复杂度 O(n) ，时间时间复杂度 O(n2)

完全没思路，值得二刷

树的题目，用递归，基于二叉搜索树的性质和后序遍历的性质。

class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        int n = sequence.size();
        if(n == 0) return false;
        return check(sequence, 0, n-1);
    }
    // 后序遍历，左右根，二叉搜索树，左<根<右
    bool check(vector<int>& S, int l, int r){
        if(l>=r) return true;
        
        int root = S.at(r);
        int j = r - 1;
        int i = l;
        
        //划分出左右子树
        //划分右子树
        while(j >= 0 && S.at(j) >= root){
            j--;
        }
		//划分左子树
        while(i <= j){
            if(S.at(i) > root) return false;
            ++i;
        }
        
        return check(S, l, j) && check(S, j+1, r - 1);
    }
};

时间复杂度：O(n^2), n为二叉树节点的个数, 当树为链式时时间复杂度最坏为O(n^2) 空间复杂度：O(n), 当树为链式结构时, 递归深度为n

还有另一种用辅助栈的方法，没敲，贴这里。 时间复杂度：O(nlogn), 时间复杂度取决于排序。空间复杂度：O(n), 额外数组和辅助栈的空间。

class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        if(sequence.empty()) return false;
        vector<int> inorder(sequence);
        sort(inorder.begin(), inorder.end());
        return IsPopOrder(inorder, sequence);
    }
 
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
         int n = pushV.size();
         stack<int> stk;    // 使用STL中的栈容器
         int i = 0, j = 0;
         while(i < n){
             stk.push(pushV[i]);    // 首先将pushV[i]入栈
             while(!stk.empty() && stk.top() == popV[j]){    // 不断检查栈顶
                 ++j;
                 stk.pop();
             }
             ++i;
         }
         return j == n;    // 判断能否成功对应
     }
};