学步园

#include <iostream>
using namespace std;
/**
* 给定一个序列，判断其是不是某个BST的后序遍历输出
* 思想： 根据在位于序列最后的根节点，将序列划分成两个part。
*		 然后判断后半序列是否都比root大，如果不是，则返回false。(前半序列一定都比root小)
*		 如果当前序列满足BST左右子树两个part的性质，继续递归两个part。
*/
bool judgepostorder(int *a, int n){

	//注意边界条件
	if(n ==0 || n == 1) return true;
	
	int root = a[n-1];
	//找到划分点(第一个大于root的点)
	for(int i=0;i<n-1;i++){
		if(a[i] > root){
			break;
		}
	}

	//如果存在后半序列，则判断是否都大于root
	if(i != n-1){
		for(int j=i+1;j<n-1;j++){
			if(a[j] < root) return false; //不满足
		}
	}

	//各自递归
	return judgepostorder(a, i) && judgepostorder(a+i, n-i-1);
}

int main(){
	int a[] = {2,4,5,3,9,13,8,6};
	int b[] = {2,4,5,3,8,9,3,6};
	int c[] = {0};
	//int d[] = {};
	int f[] = {2,2,2,2};

	cout<<judgepostorder(a, 8)<<endl;	//1
	cout<<judgepostorder(b, 8)<<endl;	//0
	cout<<judgepostorder(c, 1)<<endl;	//1
//	cout<<judgepostorder(d, 0)<<endl;
	cout<<judgepostorder(f, 4)<<endl;	//1
		
	return 0;
}