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

题目描述：

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。

参考以下这颗二叉搜索树：
     5
    / \
   2   6
  / \
 1   3
 
输入: [1,6,3,2,5]
输出: false

输入: [1,3,2,6,5]
输出: true

提示：数组长度 <= 1000

解法1：递归（左闭右开）

class Solution {
public:
    bool verifyPostorder(vector<int>& postorder) {

        return dfs(postorder, 0, postorder.size());
    }

    bool dfs(vector<int>& postorder, int start, int size) {
   
        //左闭右开固定写法
        if (start + 1 > size) return true;

        //在后序遍历得到的序列中，根结点是最后一个元素
        int root = postorder[size - 1];  

        //左子树都比根结点小，右子树都比根结点大
        int i = start;
        while (i < size && postorder[i] < root) ++i;  //i = 3

        //j = i，此时j指向右子树，右子树的值一定比根节点大，如果右子树的值比根节点小，返回false
        for (int j = i; j < size; ++j){
            if (postorder[j] < root) return false;
        }

        //递归：左闭右开
        return dfs(postorder, start, i) && dfs(postorder, i, size - 1);
    }
};