题目描述

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

class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        //二叉搜索树根节点左侧节点值均比根节点值小
        //二叉搜索树根节点右侧节点值均比根节点值大
        //后续遍历最后一个值是根节点值
        if(sequence.empty())
            return false;
        return judge(sequence, 0, sequence.size() - 1);
    }

    bool judge(vector<int>& sequence, int left, int right) {
        if(left >= right)
            return true;
        int index = left;
        while(index < right && sequence[index] < sequence[right])
            ++index;
        for(int i = index; i < right; ++i) {
            if(sequence[i] < sequence[right])
                return false;
        }
        return judge(sequence, left, index - 1) &&
            judge(sequence, index, right - 1);
    }
};