剑指offer JZ28 二叉搜索树的后序遍历序列

题目描述：
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true,否则返回false。假设输入的数组的任意两个数字都互不相同。（ps：我们约定空树不是二叉搜素树）

思路：
一、递归
二叉搜索树的左右子树都是二叉搜索树，因此可以利用递归，判断每个子树是不是二叉搜索树
利用一个辅助函数，实现递归
首先判断这个数组的根节点是否满足二叉搜索树的要求
然后可以拆成左右子树，再对左右子树进行同样的判断

class Solution {
public:
    bool help(vector<int>a,int l,int r){
        if(l>=r) return true;
        int i=r;
        while(i>l&&a[i-1]>a[r]) i--;
        for(int j=i-1;j>=l;j--){
            if(a[j]>a[r]) return false;
        }
        return help(a,l,i-1)&&help(a,i,r-1);
    }
    bool VerifySquenceOfBST(vector<int> sequence) {
        if(sequence.size()<1) return false;
        return help(sequence,0,sequence.size()-1);
    }
};

二、非递归
跟递归一样，同样是判断根节点是否满足要求（左子树的所有节点都小于根节点；右子树的所有节点都大于根节点）

代码如下：

class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        int n=sequence.size();
        if(n==0) return false;
        int i=0;
        n-=1;
        while(n){
            while(sequence[i]<sequence[n]){//这部分是左子树
                i++;
            }
            while(sequence[i]>sequence[n]){//这部分是右子树
                i++;
            }
            if(i<n) return false;//左子树部分+右子树部分=数组长度-根节点
            i=0;
            n--;
        }
        return true;
    }
};