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

class Solution {
public:
    /*
    二叉搜索树后序遍历特点：最后一个数字是树的根节点的值。数组中前面两部分的数字可以分为两部分：
    第一部分是左子树节点的值，他们都比根节点的值小；第二部分是右子树节点的值，他们都比根节点的值大。
    所以本题可以考虑用递归解答。
    */
    bool VerifySquenceOfBST(vector<int> sequence) {
        int len = sequence.size();
        if (len <= 0||sequence.empty())
            return false;
        return VerifyLeftAndRightSequenceOfBST(sequence, 0, len - 1);
    }

    /*
    注意将数组分左右部分时不能简单地取中值，因为二叉搜索树可能不对称，例如说4,6,7,5这类，
    其左子树只有一个节点，右子树有两个节点。所以更准确的方法是遍历列表，找到第一个大于根节点的即为右半部分起始点。
    以这个点分开左右部分。
    另外，退出循环的条件start>=end;这是根绝实际条件判断的。仅仅是等于还不足以概括所有情况。例如当一个根没有左子树只有右子树时。
    */
    //取出数组单独一截进行遍历，判断是否符合条件
    bool VerifyLeftAndRightSequenceOfBST(vector<int> sequence, int start, int end)
    {
        if (start >= end)
            return true;
        //int mid = (start + end) / 2;
        //根节点即数组最后一位
        int rootValue = sequence[end];
        //遍历节点，找到左右节点的分界点
        int i = start;
        for (; i < end; i++)
        {
            if (sequence[i] > rootValue)
                break;
        }
        int mid = i;
        //遍历后面一部分节点，判断是否全部大于根节点值。若否，退出
        for (int i = mid; i < end; i++)
        {
            if (sequence[i] <= rootValue)
                return false;
        }
        return VerifyLeftAndRightSequenceOfBST(sequence, start, mid - 1)
            && VerifyLeftAndRightSequenceOfBST(sequence, mid, end - 1);
    }
};