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

class Solution {
public:
    bool VerifySquenceOfBST(std::vector<int> sequence) {
        int len = sequence.size();

        if(len == 0) return false;
        if(len == 1) return true;

        bool result = Helper(sequence);
        return result;

    }
private:
    bool Helper(std::vector<int> sequence){
        int len = sequence.size();
        if(len == 1 || len == 0) return true;
        int index = len-1;


        // 提出根节点
        int rootVal = sequence.back();

        // 区分左右子树
        while (index >= 0)
        {
            if(sequence[index] < rootVal){  // 0~index 左子树 index+1~end-1 右子树
                break;
            }
            else index--;
        }
        // 检查左子树中是否有大于根节点的元素
        for (int i = index; i>=0; i--) {
            if (sequence[i] > rootVal) {
                return false;
            }
        }

        std::vector<int> leftSubtree(sequence.begin(), sequence.begin()+index+1);
        std::vector<int> rightSubtree(sequence.begin()+index+1, sequence.end()-1);
        
        // 递归检查左右子树
        return Helper(leftSubtree) &&
               Helper(rightSubtree);
    }

};