思路:
    时间复杂度:O(nlogn)
    后序遍历序列的最后一个值是根节点,又由于是二叉搜索树,则比根节点值小的在左子树,其余的在右子树。

    1. bool VerifySquenceOfBST(vector<int> sequence) {
    2. if(sequence.empty())return false;
    3. return isSequenceOfBST(sequence, 0, sequence.size() - 1);
    4. }
    5. bool isSequenceOfBST(vector<int> sequence, int start, int end){
    6. if(start >= end - 1)return true;
    7. int mid = 0, i = start;
    8. for(;i < end;i++){
    9. if(sequence[i] > sequence[end]){
    10. mid = i;
    11. break;
    12. }
    13. }
    14. for(;i < end;i++){
    15. if(sequence[i] < sequence[end])break;
    16. }
    17. if(i != end)return false;
    18. else return isSequenceOfBST(sequence, start, mid - 1) && isSequenceOfBST(sequence, mid, end - 1);
    19. }

    二叉搜索树可以为空阿!
    但是题目中序列为空时输出的是false