33-二叉搜索树的后序遍历序列

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

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

参考以下这颗二叉搜索树：

    5
   / \
  2   6
 / \
1   3

示例 1：

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

method

后序遍历最后一个节点是根节点，在前面找第一个大于根节点的数，则这个数之前是左子树，之后是右子树，如果右子树中有小于根节点的值，就不是二叉搜索树

如果后序遍历是递增的，i会遍历到r本身，然后不进入j的循环，这样左边递归处理[l,r-1]，右边递归处理[r,r-1]直接返回true

bool dfs(vector<int>& post, int l, int r) {
    if (l >= r) return true;    // [l, r]
    int root = post[r];
    int i = l;
    while (post[i] < root) i++;
    int j = i;
    while (j < r) {
        if (post[j++] < root) return false;
    }
    bool left = dfs(post, l, i - 1);
    bool right = dfs(post, i, r - 1);
    return left && right;
}
bool verifyPostorder(vector<int>& postorder) {
    int n = postorder.size();
    return dfs(postorder, 0, n - 1);
}