二叉搜索树的后续遍历

递归求解，左右子树保存下来，递归判断左子树和右子树是否为搜索二叉树

class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        if(sequence.empty()) return false;
        return __VerifySquenceOfBST(sequence);
    }


    bool __VerifySquenceOfBST(vector<int> sequence){
        if(sequence.empty() || sequence.size() == 1) return true;
        int root = *(sequence.end()-1);
        vector<int> left;
        vector<int> right;
        int index = 0;
        for(int i = 0 ; i<sequence.size()-1;i++){
            if(sequence[i] < root) {
                left.push_back(sequence[i]);
                index ++;
            }else if(sequence[i] == root){
                return false;
            }else{
                break;
            }
        }

        while(index < sequence.size() - 1){
            if(sequence[index] > root){
                right.push_back(sequence[index]);
                index ++;
            }else{
                return false;
            }
        }

        return __VerifySquenceOfBST(left) && __VerifySquenceOfBST(right);
    }
};

改进：