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

解题思路：

1. 后序遍历最后一个值是根节点。
2. 左子树的值一定小于等于根节点，右子树的值一定大于等于根节点，根据这一个特点可以分出左子树和右子树。
3. 递归判断左子树和右子树是否满足上面的条件，只有全部满足，才为搜索二叉树，否则不是搜索二叉树。

class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        // 约定空树不是二叉搜索树
        if(sequence.size() == 0) return false;
        // 只有两个或者一个节点，不需要验证
        if(sequence.size() <= 2) return true;
        // 进入递归验证
        return verifySubTree(sequence, 0, sequence.size()-1);
    }
    
    bool verifySubTree(vector<int> & sequence, int startPos, int endPos) {
        // 只有两个或者一个节点，不需要验证
        if(endPos - startPos <= 1) return true;
        // 找到右子树的起始节点
        int rightStart = startPos;
        while(rightStart < endPos) {
            if(sequence[rightStart] > sequence[endPos]) break;
            rightStart++;
        }
        int rightEnd = endPos - 1;
        // 找到左子树的起始节点
        int leftStart = startPos;
        int leftEnd = rightStart - 1;
        // 因为判断右节点起始位置是从左向右判断的，所以左子树的所有值都小于等于根节点，不需要判断
        // 只需要判断右子树所有的值是否都大于跟节点即可
        // 如果右树存在，判断右子树的节点是否都大于根节点
        int tmpPos = rightStart;
        while(tmpPos <= rightEnd) {
            if(sequence[tmpPos] < sequence[endPos]) return false;
            tmpPos++;
        }
        // 判断左右子树是否满足条件
        return verifySubTree(sequence, leftStart, leftEnd) && verifySubTree(sequence, rightStart, rightEnd);
    }
};