学步园

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

记住是二元查找树 根大于左边 小于右边而且是后序，
所以思序列最后一个必是根节点，从前往后遍历，比根节点小的都是其左子树，
并且位于序列的左半部分，比其大的为其右子树，应该位于其右半部分。
递归左右子树按上述思路分别进行判断。 
*/ 
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std; 

void test(int data[],int st,int end,bool &flag)
{
	if(flag&&st<end)
	{
		int	left=st;
		while(data[end]>data[left]) left++;//取左子树
		
		for(int j=left;j<end;j++)// 判断右子树是否合格 
		{
			if(data[j]<data[end])
			{
				flag=false;return;
			}
		} 
		
		test(data,0,left-1,flag);// 递归判断 
		test(data,left,end-1,flag);
	}
}

int main(){
	
	int a[]={5,7,6,9,11,10,8};
	bool flag=true;
	test(a,0,6,flag);
	if(flag) cout<<"yes"<<endl;
    	else  	cout<<"no"<<endl;
		
    int b[]={7,4,6,5};
    test(b,0,3,flag);
    if(flag) cout<<"yes"<<endl;
    	else cout<<"no"<<endl;
	return 0;
}