题解 | #二叉搜索树的后序遍历序列#

刚看到题目尝试使用迭代的方法来找规律逐个元素判断，写到后面发现情况太过复杂，还是递归来的方便。
总体思路是后序遍历的搜索树，其最后一个结点为头结点，而前面的数列则可根据该头结点分为连续的两部分，一部分笔比该结点大，一部分比该结点小。
这样就得到了基本的拆分思路，每次都找到数列最后一个数，然后找到数列中第一个比该数大的数的下标，遍历该下标之后的数，若发现比该数小的，则返回false。否则，继续拆分数列。递归调用函数判断被拆分出来的一大一小两个子数列，并取两个函数的返回值的并作为结果。
上面给出了递归的总体框架，还缺少结束条件，我们发现，只要数列的长度小于3，无论如何它都是一个合理的搜索树，所以结束条件就是当数列大小小于3时，返回true。
这里面还有一些细节判断需要细心，比如空树判断，单边树判断，数组的截断位置。
最开始看到题目中的考点有栈，想了一会用栈怎么实现，最后还是选择了递归，不过递归也用到了栈，勉强解释的通。

class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        if(sequence.size() == 0){
            return false;
        }
        else if(sequence.size() < 3){
            return true;
        }
        int root = sequence.at(sequence.size()-1);
        int index = 0;
        for(;index<sequence.size()-1;index++){
            if(sequence.at(index)>root){
                break;
            }
        }
        if(index == sequence.size()-1){
            return true;
        }
        for(int i = index; i < sequence.size()-1;i++){
            if(sequence.at(i)<root){
                return false;
            }
        }
        vector<int>::const_iterator it1 = sequence.begin();
        vector<int>::const_iterator it2 = sequence.begin() + index;
        vector<int> s1(it1,it2);
        vector<int>::const_iterator it3 = sequence.end() - sequence.size() + index;
        vector<int>::const_iterator it4 = sequence.end() - 1;
        vector<int> s2(it3,it4);
        if(s1.size() == 0){
            return VerifySquenceOfBST(s2);
        }
        if(s2.size() == 0){
            return VerifySquenceOfBST(s1);
        }
        return VerifySquenceOfBST(s1) && VerifySquenceOfBST(s2);
    }
};