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

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。

如果是则返回true，否则返回false。

假设输入的数组的任意两个数字都互不相同。
样例

输入：[4, 8, 6, 12, 16, 14, 10]

输出：true

分析：
二叉搜索树的左子树的数都比根节点的数小，右子树的数都比根节点的数大

1.利用后序遍历的性质，首先数组的最后一个数就是树的根节点；
2.遍历数组，从左到右找出比根节点小的最后一个数（以该数为分割，该数的左边就是左子树（包括该数），该数的右边就是右子树）
3.遍历当前的右子树，只要有一个数不满足（所有的右子树的数都大于根节点的数）；
4.如果上面满足，就继续递归下一层，知道整个数组为空（l>=r）时，即所有的数都满足，返回true。

时间复杂度
遍历整个数组，时间复杂度为O（N）

class Solution {
public:
    vector<int> seq;
    bool verifySequenceOfBST(vector<int> sequence) {
        seq = sequence;
        return dfs (0, seq.size()-1);
    }
    
    bool dfs(int l, int r) {
        if(l >= r) return true;
        int root = seq[r];
        int k = l;
        while(k<r && seq[k] < seq[r]) k++; //找出比根节点小的最右边的一个数
        //此时k位于右子树的第一个位置
        //遍历右子树，看右子树的所有结点是否都大于根节点的值，
        //若小于，则返回false
        //若大于，则说明当前层符合要求，继续进行下一次的递归
        for(int i = k; i<r;i++) {
            if(seq[i] < seq[r]) return false;
        }
        return dfs(l, k-1) && dfs(k, r-1);
    }
};