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

• 序列长度为0，返回false；
• 序列长度为1，返回true；
• 后序遍历的最后一个元素为根节点，二叉搜索树左子节点元素一定小于根值，右子节点元素一定大于根值；
• 递归判断左子树和右子树。

class Solution {
public:
    bool VerifySquenceOfBSTMin(vector<int> sequence, int start, int end) {
        if (start >= end) return true;
        int low = start;
        while (low < end && sequence[low] < sequence[end]) ++low;
        for (int i = low; i < end; i++) {
            if (sequence[i] < sequence[end]) return false;
        }
        return VerifySquenceOfBSTMin(sequence, start, low - 1) &&
            VerifySquenceOfBSTMin(sequence, low, end - 1);
    }
    bool VerifySquenceOfBST(vector<int> sequence) {
        if (sequence.size() == 0) return false;
        if (sequence.size() == 1) return true;
        return VerifySquenceOfBSTMin(sequence, 0, sequence.size() - 1);
    }
};