题目描述

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

思路

首先，要知道什么是二叉搜索树：对于任何一棵子树来说，根节点都比它的左子树大，比它的右子树小
二叉搜索树有什么特点呢？
下面是一棵二叉搜索树：

            10
           /  \
          8   13
         / \  / \
        7  9 11 17

前序遍历：10,8,7,9,13,11,17；
第一个是根节点，后面分别为它的左右子树(左都比它小，右都比它大)
中序：7,8,9,10,11,13,17；
中序遍历单调递增
后序遍历：7,9,8,11,17,13,10
最后一个节点是根节点，前面分别为它的左子树和右子树(左都比它小，右都比它大)

用递归的思想
关键点：
（1）找这个序列中左右子树的分界点
（2）递归分别判断左右子树

我的错误：
未考虑特殊情况(没有左子树或者没有右子树的情况)
一开始我的bound没有给初始值，所以出错了，不能只想着最一般的情况！！！

代码

class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        if(sequence.size()<=0)
            return false;
        int left=0;
        int right=sequence.size()-1;
        return Verify(sequence,left,right);
    }

    bool Verify(vector<int> sequence,int left,int right)
    {
        if(left>=right)
            return true;
        int root=sequence[right];
        int flag=0;  //标志出现了比根节点大的数，0表示没有出现，1表示出现了
        int bound=0;  //定义小于和大于之间的边界
        for(int i=left;i<right;i++)
        {
            if(sequence[i]>root && flag==0)
            {
                bound=i;
                flag=1;   //出现之后flag变为1
            }
            else if(sequence[i]<root && flag==1)
                {
                    return false;       //如果在flag=1(已经有比根节点大了数了还出现了比根节点小的，那就返回false)
                }
        }
        return Verify(sequence,left,bound-1)&& Verify(sequence,bound,right-1);

    }
};