[数据结构与算法]剑指 Offer 33. 二叉搜索树的后序遍历序列

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

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

? ? ?5
? ? / \
? ?2 ? 6
? / \
?1 ? 3
示例 1：

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

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

提示：

数组长度 <= 1000

首先要知道的是，二叉搜索树的特征就是左子树的所有结点都比根节点小，而右子树的所有结点都比根节点大。所以对于任一序列，取其最后一个结点为根节点，然后从序列头部开始遍历，直到根节点或者遇到比根节点大的值停止，此处为左右子树的分界点，然后对左子树序列和右子树序列递归进行同样的操作。

class Solution {
public:
    bool verifyPostorder(vector<int>& postorder) {
        int len = postorder.size();
        return dfs(postorder, 0, len-1);
    }
    bool dfs(vector<int>& postorder, int l, int r) {
        if (l > r) return true;
        int root = postorder[r];
        int i = l;
        while (postorder[i] < root) i++;
        if (i > r) return true;
        for (int j = i; j <= r; ++j) {
            if (postorder[j] < root) return false;
        }
        return (dfs(postorder, l, i-1) && dfs(postorder, i, r-1));
    }
};