给定序列，判断是否为BST后续遍历结果

判断整数序列是不是二元查找树的后序遍历结果
题目：输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。
如果是返回true，否则返回false。
例如输入5、7、6、9、11、10、8，由于这一整数序列是如下树的后序遍历结果：

8
/ \
6 10
/ \ / \
5 7 9 11
因此返回true。
如果输入7、4、6、5，没有哪棵树的后序遍历的结果是这个序列，因此返回false

最后一个节点a[n]一定是根节点。是后序遍历的结果的充要条件是：前面的数组可以分为小于a[i]和大于a[i]的两部分，并且分别都是后序遍历的结果。所以可以用O(n)来判断是否能分成两部分，再递归判断剩下的两部分，T(n)=T(k)+T(n-k)+O(n)，这个应该和快排的复杂度是一样的，O(nlogn)期望，O(n^2) worst case。我相信利用二分可以将上式变为T(n)=T(k)+T(n-k)+O(logn)，但需要非常小心来保证正确性。

最后一个节点a[n]一定是根节点。是后序遍历的结果的充要条件是：前面的数组可以分为小于a和大于a的两部分，并且分别都是后序遍历的结果。所以可以用O(n)来判断是否能分成两部分，再递归判断剩下的两部分，T(n)=T(k)+T(n-k)+O(n)，这个应该和快排的复杂度是一样的，O(nlogn)期望，O(n^2) worst case。我相信利用二分可以将上式变为T(n)=T(k)+T(n-k)+O(logn)，但需要非常小心来保证正确性。
darksteel 发表于 2011-5-24 09:12

    解答和时间复杂度的分析都很准确，very good!!

bool __inner_judge(int a[], int n);

bool IsBSTPostOrder(int a[], int n)
{
        assert(a);
        assert(n>0);

        return __inner_judge(a, n);
}

bool __inner_judge(int a[], int n)
{
        if (0 == n) return true;

        int nRoot = a[n-1];
        int nIter = 0;
        while (nIter < n-1 && a[nIter] <= nRoot)
                nIter++;

        int i = nIter;
        while (i < n-1)
        {
                if (a[i] <= nRoot)
                        return false;
                i++;
        }

        return __inner_judge(a, nIter) && __inner_judge(a+nIter, n-nIter-1);
}

post我的代码