100题_06 判断整数序列是不是二元查找树的后序遍历结果

   6   10

  / \   / \

 5 7  9 11
因此返回true。

这题其实很简单，我们知道二元查找树的中序遍历是有序的。给定后续遍历结果，排序后可得到终须遍历结果。有了中序遍历结果和后续遍历结果，我们就可以确定一颗二叉树。其实这题目更加简单，只需要我们判定就可以了，一个二叉查找树，左边的节点一定会小于右边的节点。而后续遍历的最后一个节点就应该是根结点，因此这题可以很容易地用递归的思想解决。

代码如下：

View Code #include <iostream>

using namespace std;

bool IsSearchBinaryTree(int a[], int n)
{
    if (n == 0)
        return true;
    if (n < 3)
        return false;
    if (n == 3)
    {
        if (a[0] < a[2] && a[1] > a[2])
            return true;
        else
            return false;
    }
    int i;
    for (i = 0; i < n-1; i++)
    {
        if (a[i] < a[n-1])
            continue;
        else
            break;
    }
    return IsSearchBinaryTree(a, i) && IsSearchBinaryTree(a + i, n - i - 1);
}

int main()
{
    int a[] = {5,6,7,9,11,10,8};
    cout<<IsSearchBinaryTree(a, 7)<<endl;
    return 0;
}