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

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

思路：

因为是后续遍历，所以数组最后一个数就是根节点。从前往后扫描数组，如果某个数大于根节点的值，则停下，记这个数的下标为index,则index之前的数是左子树，然后继续扫描，如果出现小于根节点的数，则说明不是二叉搜索树的后序遍历结果，返回false，如果都大于根节点，则从index开始到根节点前一个数是右子树。对于左子树和右子树使用上述操作。

代码：

class Solution {
public:
    bool verifyPostorderRes(vector<int>& postorder,int left, int right) {
        int index = left;
        for(;index < right;index++) {
            if(postorder[index] > postorder[right]) {
                break;
            }
        }
        for(int i = index;i < right;i++) {
            if(postorder[i] < postorder[right]) {
                return false;
            }
        }
        bool leftResult = true;
        if(index > left) {
            leftResult = verifyPostorderRes(postorder,left,index-1);
        }
        bool rightResult = true;
        if(index < right) {
            rightResult = verifyPostorderRes(postorder,index,right-1);
        }
        return leftResult && rightResult;
    }
    bool verifyPostorder(vector<int>& postorder) {
        int length = postorder.size();
        if(length == 0) return true;
        return verifyPostorderRes(postorder,0,length-1);
    }
};