二叉树搜索树的后续遍历（递归+非递归）

/*
每次递归划分出左右子树进行判断
根据最后一个元素根节点，划分左子树，剩下的为右子树，判断右子树是否符合条件。
然后递归判断左右子树.
边界条件：eg当left=2，sequence[left]=5,right=3,sequence[right]=5；
i=3,递归进去左子树f(sequence,3,2);
*/
class Solution {
public:
    bool f(vector<int> &sequence, int left, int right){
        if(left>=right)return true;//left>=right,当没有左子树时left>right.
        int i=left;
        for(;i<=right&&sequence[i]<sequence[right];i++);//i<=right当全部是右子树
        for(int j=i;j<right;j++)if(sequence[j]<sequence[right])return false;
        return f(sequence,left,i-1)&&f(sequence,i,right-1);
       //当循环不执行是i=left,则i-1<left，同理可能right-1<i
    }
    bool VerifySquenceOfBST(vector<int> sequence) {
       if(!sequence.size())return false;//为空直接返回
        return f(sequence,0,sequence.size()-1);//调用递归函数
    }
/*
用栈模拟，先根节点，在右子树再左子树。按照根节点，右子树的关系建立树，用左子树节点是否符合判断是否正确。
每次要走左子树时候，更新max，接下来遍历的所有节点都要小于max,否则return false
出栈时，找到当前节点最小的祖先节点，并更新max。
*/
    bool VerifySquenceOfBST2(vector<int> &s) {
        if (!s.size()) return false;
        stack<int> roots;
        roots.push(INT_MIN);
        int max = INT_MAX;
        for (int i=s.size()-1; i >= 0; i--) {//每次循环是一个递归过程，从根节点深入右子树
            if (s[i] > max) return false;//右子树中有节点值大于根节点
            while (s[i] < roots.top()) {//进入左子树，找到该节点的最大祖辈
                max = roots.top();//当走左子树的时候才更新max值，这是要遍历节点的上线。
                roots.pop();
            }
            roots.push(s[i]);//该节点成为新的根节点。
        }
        return true;
    }


};