题解 | 二叉搜索树的后序遍历序列

class Solution {
public:
    //二叉搜索树：左子树全部小于根节点值，右子树全部大于根节点值
    //后序遍历，数组的最后一个值就是根节点；
    //通过找出左子树，再检测右子树的办法，然后进行递归分治
    bool VerifySquenceOfBST(vector<int> sequence) {
        int n = sequence.size();
        if(n == 0)return false;

        return checkif(sequence, 0, n-1);
    }

    bool checkif(vector<int>& sequence, int start, int end){
        if(start >= end)return true;  //可能出现只有单边子树的情况，那么它会出现边界不合法的情况

        int rootval = sequence[end];

        int i=start;  //划分出左子树
        while(sequence[i] < rootval){
            i++;
        }

        for(int j=i; j<end; j++){
            if(sequence[j] < rootval)return false;
        }

        return checkif(sequence, start, i-1) && checkif(sequence, i, end-1);
    }
};