剑指 Offer 33. 二叉搜索树的后序遍历序列

剑指 Offer 33. 二叉搜索树的后序遍历序列

思路：

二叉搜索树后中左子树 < 根节点 < 右子树，后序遍历中，最后一个点是根节点，前一部分小于根节点是左子树，中间的大于根节点是右子树，递归判断是不是符合这个条件。

代码：

class Solution {
public:
    bool verifyPostorder(vector<int>& postorder) {
        return dfs(postorder,0,postorder.size()-1);
    }

    bool dfs(vector<int> & postorder,int l,int r){
        if(l >= r) return true;
        int root = postorder[r];
        int k = l;
        while(k < r && postorder[k] < root) k++;
        int mid = k;
        while(k < r && postorder[k] > root) k++;
        return k == r  && dfs(postorder,l,mid - 1) && dfs(postorder,mid,r - 1);
    }
};