[剑指offer 编程题]二叉搜索树的后序遍历序列

class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        //二叉搜索树的后序遍历的特征，左右根
        //往前找，第一个比它小的是它的左子树，第一个比它大的是它的右子树。

        if(sequence.size() == 0)return false;
        if(sequence.size() == 1)return true;

        int length = sequence.size();  

        return find_in_order(sequence,length-1,0);
    }

    bool find_in_order(vector<int> sequence,int index,int start){

        if(index == start) return true;

        int left,right = -1;

        for(int i = index - 1;i >= start;i--){//往前找，第一个比它大的是它的右子树
            if(sequence.at(i) > sequence.at(index)){                
                right = i;
                break;
            }
        }

        for(int j = index - 1;j >= start;j--){//往前找，第一个比它小的是它的左子树
            if(sequence.at(j) < sequence.at(index)){                
                left = j;
                break;
            }
        }

        bool left_area,right_area = true;

        if(left != -1){
            left_area = if_small(sequence,start,left,sequence.at(index));

            if(right != -1){//左右子树都有
                right_area = if_large(sequence,left+1,right,sequence.at(index));
                if(!left_area || !right_area)return false;
                return find_in_order(sequence,left,start) && find_in_order(sequence,right,left+1);
            }//right!=-1
            else{//只有左子树
                if(!left_area)return false;
                return find_in_order(sequence,left,start);
            }

        }//left!=-1
        else{//只有右子树
           if(right != -1){
               right_area = if_large(sequence,start,right,sequence.at(index));
               if(!right_area)return false;
                return find_in_order(sequence,right,start);
           } 
        }

    }

    bool if_small(vector<int> sequence, int start, int end,int val){
        for(int i = start;i<=end;i++){
            if(sequence.at(i)>val)return false;
        }
        return true;
    }

    bool if_large(vector<int> sequence, int start, int end,int val){
        for(int i = start;i<=end;i++){
            if(sequence.at(i)<val)return false;
        }
        return true;
    }
};