剑指offer 33 数列是否是二叉搜索树的后续遍历

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

关键在于掌握知识点: 二叉搜索树是左子树比根节点小, 右节点比根大.

思路: 从最后一个元素检查, 找到所有比自己大的集合, 在那个位置再向前找所有元素是否都比自己小.
这个过程递归.

bool verifyPostorder(int* postorder, int postorderSize){
    if(!postorder || postorderSize == 0) return true;
    if(postorderSize == 1) return true;

    int cut = postorderSize - 2;
    int count = 0;
    int result = 1;

    while(cut >=0 && postorder[cut] > postorder[postorderSize - 1])
    {
        cut--;
        count++;
    }
    if(count) result &= verifyPostorder(&postorder[cut + 1], count);

    for(int i = 0; i <= cut; i++)
    {
        if(postorder[i]>postorder[postorderSize - 1])
            return false;
    }
    result &= verifyPostorder(postorder, postorderSize - 1 - count);

    return result;

}

时间复杂度: N2
空间复杂度: N

另一个思路是: 将序列倒过来看, 那么就是跟->右子树->左子树, 这是一个递增的数列, 直到遇到了左子树, 每一次找到符合的右子树, 就将自己放入栈中.
遇到不符合单调递增的节点, 证明这是一个左子树, 左子树的位置从栈中找, 这个位置应该比当前栈顶元素小, 比下一个栈内元素大. 位置就是栈顶元素的左子树. (唯一false判断条件: 后续所有节点都不可能比这个节点大!) 找到之后, 将该节点入栈.

时间复杂度 N *2
空间复杂度: N 最坏的时候都是右子树, 全都入栈