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

• 后序遍历二叉树的性质是，根节点肯定在最后。这样就为递归解决提供了可能。
• 找到根后，从左往后走，小于根的是左子树，大于根的是右子树。注意：如果右子树中出现了小于根的数，那就判否了。
• 细节方面，需要主要几个特例：如size=0,1,2，怎么处理？0=false，1/2=true。

class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        if(sequence.empty()) return false;
        int size = sequence.size();
        if(1==size) return true;
        if(2==size) return true;
        int root = sequence[size-1];
        vector<int> left;
        vector<int> right;
        bool bLeftOver = false;
        for(int i=0; i<size-1; ++i){
            if(sequence[i] < root){
                if(!bLeftOver)
                    left.push_back(sequence[i]);
                else
                    return false;
            }
            else{
                if(!bLeftOver)
                    bLeftOver = true;
                right.push_back(sequence[i]);
            }
        }
        if(left.size()){
            if(!VerifySquenceOfBST(left))
                return false;
        }
        if(right.size()){
            if(!VerifySquenceOfBST(right))
                return false;
        }
        return true;
    }
};