class Solution {
public:
    /* 搜索二叉树的后序遍历结果，当前根结点左儿子下标，一定是
     * 最后一个小于根节点元素的下，右儿子下标，一定是大于根节点的最后一个元素下标
     *  4，8，6，12，16，14，10      子结点查找范围    
     *       左         右  根     （left---right)
     *  4，8，6，12，16，14 
     *  左 右 根                   （0---nextl)左子树
     *  4，8，6，12，16，14         
     *          左  右  根         （nextr----right-1)右子树
     *  由此以来，不满足这种性质的nextl、nextr直接return false;
     *  或者说： 只要nextl > nextr  return false
     *  结尾附 根据后序结果建立一个搜索二叉树
     */
    bool isBST(vector<int>& seq,int left,int right){
            if(left > right){ //找完了就是true
                return true;
            }
            int nextl = -1;int nextr = right;
            for(int i = left;i<=right;i++){
                if(seq[i] < seq[right]){
                    nextl = i;
                }if(seq[i] > seq[right]){
                  //下面这一行是找右子树的左边界，
                  //也可以重新遍历 找到第一个大于根节点的后直接 break； 
                    nextr = nextr==right ? i:nextr;
                }
            }
            if(nextl > nextr){ //上面提到的条件
                return false;
            }
            return isBST(seq, left, nextl)&&isBST(seq, nextr, right-1);
    }
    
    
    bool VerifySquenceOfBST(vector<int> sequence) {
        //TreeNode* head =  creatTree(sequence, 0,sequence.size()-1);
        if(sequence.size() <= 0){
            return false;
        }
        return isBST(sequence, 0, sequence.size()-1);
        
   }
    
  
    //附 ： 根据后序遍历结果创建搜索二叉树
    TreeNode* creatTree(vector<int>& arr,int left,int right){
        if (left > right){
            return nullptr;
        }else{
            TreeNode* node = new TreeNode(arr[right]);
            int nextl = -1;
            int nextr = right;
            for(int i = left;i<=right;i++){
                if(arr[i] < node->val){
                    nextl = i;
                }if(arr[i] > node->val){
                    //右子树的左边界,也可以重新遍历，找到就break;
                    nextr = nextr == right ? i:nextr; 
                }
            }node->left = creatTree(arr, left, nextl);
            node->right = creatTree(arr, nextr , right-1);
            return node;
        }
    }
};