（十六）剑指offer之二叉搜索树的后序遍历序列

题目描述：

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

class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
  int length = sequence.size();
        return verifySequence(sequence, length);
    }

    bool verifySequence(vector<int> sequence, int length){
        if(sequence.empty() || length <= 0) return false;
        vector<int> rightSequence;
        int root = sequence[length-1];
        int i = 0;
        for(; i<length-1;i++){
            if(sequence[i]>root)
                break;
        }
        int j = i;
        for(; j<length-1;j++){
            if(sequence[j] < root)
                return false;
            rightSequence.push_back(sequence[j]);
        }
        bool left = true;
        if(i>0)
         left = verifySequence(sequence, i);

        bool right = true;
        if(i<length-1)
         right = verifySequence(rightSequence, length-i-1);

        return (left && right);
    }
};

如有建议或其他问题，可随时给我们留言。或者到以下链接：

https://github.com/gaobaoru/code_day

Star/Fork/Push 您的代码，开源仓库需要您的贡献。

请查看Coding 题目网址和收藏Accepted代码仓库，进行coding！！！