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

//递归
class Solution {
public:
    
    bool isBST(vector<int> sequence) {
        if (sequence.empty()) return true;
        
        int rootV = sequence.back();    //取出根节点
        sequence.pop_back();
        
        int pos = 0;
        while (pos < sequence.size()) {    //找出左子树
            if (sequence[pos] > rootV) break;
            ++pos;
        }
        
        while (pos < sequence.size()) {    //右子树均大于根节点
            if (sequence[pos] < rootV) return false;
            ++pos;
        }
        
        //左子树和右子树是否是二叉搜索树
        return isBST(vector<int>(sequence.begin(), sequence.begin()+pos))
            && isBST(vector<int>(sequence.begin()+pos, sequence.end()));
    }
    
    bool VerifySquenceOfBST(vector<int> sequence) {
        if (sequence.empty()) return false;
        
        return isBST(sequence);
     }
};