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; } };