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

题目：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 tre，否则返回 false。 假设输入的数组的任意两个数字都互不相同。例如，输入数组 {5, 7, 6, 9, 11, 10, 8}，则返回 true，因为这个整数序列是下图二叉搜索树的后序遍历结果。如果输入的数组是 {7, 4, 6, 5}，则由于没有哪棵二叉搜索树的后序遍历结果是这个序列，因此返 false。

image.png

后序遍历序列 {5, 7, 6, 9, 11, 10, 8} 对应的二叉搜索树

---

在后序遍历得到的序列中，最后一个数字是树的根节点的值。数组中前面的数字可以分为两部分：第一部分是左子树节点的值，它们都比根节点的值小；第二部分是右子树节点的值，它们都比根节点的值大。

以数组 {5, 7, 6, 9, 11, 10, 8} 为例，后序遍历结果的最后一个数字 8 就是根节点的值。在这个数组中，前 3 个数字 5、7 和 6 都比 8 小，是值为 8 的节点的左子树节点；后 3 个数字 9、11 和 10 都比 8 大，是值为8 的节点的右子树节点。
我们接下来用同样的方法确定与数组每一部分对应的子树的结构。这其实就是一个递归的过程。对于序列 {5, 7, 6}，最后一个数字 6 是左子树的根节点的值。数字 5 比 6 小，是值为 6 的节点的左子节点，而 7 则是它的右子节点。同样，在序列 {9, 11, 10} 中，最后一个数字 10 是右子树的根节点，数字 9 比 10 小，是值为 10 的节点的左子节点，而 11 则是它的右子节点。

我们再来分析另一个整数数组 {7, 4, 6, 5}。后序遍历的最后一个数字是根节点，因此根节点的值是 5。由于第一个数字 7 大于 5，因此在对应的二又搜索树中，根节点上是没有左子树的，数字 7、4 和 6 都是右子树节点的值。但我们发现在右子树中有一个节点的值是 4，比根节点的值 5 小，这违背了二叉搜索树的定义。因此，不存在一棵二叉搜索树，它的后序遍历结果是 {7, 4, 6, 5}。

bool VerifySquenceOfBST(int sequence[], int length)
{
    if(sequence == nullptr || length <= 0)
        return false;

    int root = sequence[length - 1];

    // 在二叉搜索树中左子树的结点小于根结点
    int i = 0;
    for(; i < length - 1; ++ i)
    {
        if(sequence[i] > root)
            break;
    }

    // 在二叉搜索树中右子树的结点大于根结点
    int j = i;
    for(; j < length - 1; ++ j)
    {
        if(sequence[j] < root)
            return false;
    }

    // 判断左子树是不是二叉搜索树
    bool left = true;
    if(i > 0)
        left = VerifySquenceOfBST(sequence, i);

    // 判断右子树是不是二叉搜索树
    bool right = true;
    if(i < length - 1)
        right = VerifySquenceOfBST(sequence + i, length - i - 1);

    return (left && right);
}

摘抄资料：《剑指offer》