判断一个数组是不是某个二叉搜索树的后序遍历

题目描述

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

后序遍历： 左右中 （数组最后一个值就是根节点值）

二叉搜索树： 左值<中值<右值

分析：遍历数组，第一个比中间节点大的值就是右子树的开始标志 然后再判断 1、右子树值是否全部大于 根节点值 2、左序列、右序列是否是某二叉搜索树的后序遍历的结果 特殊情况： 没有左子树、没有右子树

class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        if(sequence.size()==0)return false;
        if(sequence.size()==1)return true;
        int rightIndex;
        int middle=sequence[sequence.size()-1];
        for(rightIndex=0;rightIndex<sequence.size();rightIndex++){
            if(sequence[rightIndex]>sequence[sequence.size()-1])break;
        }
        
        //0，rightIndex-1    rightIndex,sequence.size()-1
        if(rightIndex>0 && rightIndex<sequence.size()){//左右树都有都有
            for(int i=rightIndex+1;i<sequence.size()-1;i++){
                if(sequence[i]<middle)return false;
            }
            vector<int> leftChild(sequence.begin(),sequence.begin()+rightIndex);
            vector<int> rightChild(sequence.begin()+rightIndex,sequence.end()-1);
            return VerifySquenceOfBST(leftChild)||VerifySquenceOfBST(rightChild);
        }
        else if(rightIndex==0){//没左子树
            for(int i=rightIndex+1;i<sequence.size()-1;i++){
                if(sequence[i]<middle)return false;
            }
            return VerifySquenceOfBST(vector<int>(sequence.begin(),sequence.end()-1));
        }
        else{//没右子树
            return VerifySquenceOfBST(vector<int>(sequence.begin(),sequence.end()-1));
        }
        
        
        
    }
};