这里沿用传统二叉查找树(BST)的概念：所有左子树都小于根，右子树都大于根。(不止是直接孩子，还有间接孩子！)

现在给出一个整数序列，要求判断它是否是一棵二叉查找树BST的后序遍历结果。

如果去掉BST这个条件，我们一般是不能只根据后序遍历结果来确定某一棵树的。

有了BST这个条件后，我们可以这么做：

定义如下递归函数头：

int judge(int* arr, int start, int end)

(1)另root = end-1，则arr[root]为从start开始，end结束的子树的根（后序遍历么！）

(2)我们另i从start开始，一直++，直到碰到第一个arr[i]大于arr[root]的，那么此时的i已经位于右子树了。从start~i-1是左子树。

(3)显然从i~end-2是右子树，我们检查这段arr[j]，如果有发现<arr[root]的，直接返回false。（右子树必须都大于根！）

(4)递归检查左子树 judge(arr, start, i-1) 和右子树 judge(arr, i, end-2)。如果某一个judge返回0，那么返回0，两个都1返回1。

(5)如果start==end时候，或者arr==NULL时(空树也是BST的一种！)，可以直接返回1。

好了，代码如下：

#include <stdio.h>

int judge(int* arr, int start, int end)
{
	if(arr==NULL || start==end)
	{
		return 1;
	}else
	{
		// Find left sub tree(all small than root)
		int root = end-1;
		int i = start;
		int j = 0;
		for(i=start;i<root;i++)
		{
			if(arr[i]>arr[root])
			{
				break;
			}
		}
		// Check if right sub tree all bigger than root, else is fake BST
		j = i;
		for(;j<root;j++)
		{
			if(arr[j]<arr[root])
			{
				return 0;
			}
		}
		// Check left sub tree
		if(0==judge(arr, start, i-1))
		{
			return 0;
		}
		// Check right sub tree
		if(0==judge(arr, i, end-2))
		{
			return 0;
		}
		return 1;
	}	
}

int main()
{
	//int arr[7] = {5, 7, 6, 9, 11, 10, 8}; // Yes
	int arr[4] = {7, 4, 6, 5}; // Not
	printf("Is BST Post: %d \n", judge(arr, 0, sizeof(arr)/sizeof(int)-1));
	return 0;
}