学步园

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

二元查找树后序遍历的特征是，数组中最后一个数是树的跟，该序列前面的数为左子数部分的节点，后面的数为右子树节点。

递归判断左子树部分是否为二元查找树，右子树部分是否为二元查找树

若不存在左子树,则只需考虑右子树。若不存在右子树，则只需考虑左子树。

#include <iostream>  
using namespace std;  


bool isPostOrder(int *A,int m,int n){
	bool res=true;
	if(m==n)return true;
	int val=A[n];
	int l;
	for(l=m;l<n;l++){
		if(A[l]>val)
			break;
	}
	for(int r=l;r<n;r++){
		if(A[r]<val)
			return false;
	}
	//if left tree is NULL,then left tree part is post-order
	if(l>m)//left tree is not NULL
		res=res&&isPostOrder(A,m,l-1);
	////if righ tree is NULL,then right tree part is post-order
	if(l<=n-1)//right tree is not NULL
		res=res&&isPostOrder(A,l,n-1);
	return res;
}


int main()  
{  
	int arr[] = {5,9,8,11,13,12,10};  
	bool result =isPostOrder(arr,0,6);  
	if(result)  
		cout<<"YES"<<endl;  
	else  
		cout<<"NO"<<endl; 
	return 0;  
}