判断一个数组是不是排序二叉树后序遍历

碰到一个题目，判断一个数组是不是排序二叉树的后序遍历，所谓排序二叉树，指的是对于二叉树中的根节点比左子节点数值大，同时比右子节点数值小，例如[5,7,6,9,11,10,8] 就是一个排序二叉树的后序遍历，而[7,10，8,9]则不是

 

解题思维：

既然是后序遍历，则数组最后一个数值肯定是根节点，而从左到右，剩下数组元素的左侧值肯定小于根节点值，而其余的数组元素则大于根节点，例如[5,7,6,9,11,10,8]这个数组，8肯定是根节点，而从数组左侧到5~6三个数比8小，肯定是左子树，而剩下的9~10应该就是右子树，右子树应该满足每个数字都比根节点大，如果满足的话，我们再把[5,7,6]和[9,11,10]两个部分的数组元素重复进行之前的操作，知道结束

 

按照这个思路分析一下[7,10,8,9]为什么不是，首先9为根节点，从数组左侧找到比8小的元素组，该元素组的最后一个元素是7，因此，左子树应该是7，而剩下的[10,8,9]应该是右子树，右子树应该满足的条件是每个数字都比根节点9大，然而8比9小，所以不满足

 

了解这点的话可以写出如下程序

/*
author:luchi
date:2015/10/21 
*/ 
#include<iostream>
using namespace std;
//判断函数 
bool isValidate(int a[],int begin,int end){
	
	//如果begin>=end表示待分析的数组元素部分只有一个值或者没有值，返回true 
	if(begin>=end) return true;
	//找到根节点 
	int root=a[end];
	int i=begin;
	//找到最后一个比根节点小的元素位置 
	while(a[i]<=root){
		i++;
	}
	int seperator=i;
	//递归判断左边是不是满足 
	bool isLeftValidate=(a,begin,seperator-1);
	
	bool isRightValidate=true;
	//判断右边节点是不是比根节点大，如果不是的话，表示右边不满足，返回false 
	for(int j=seperator;j<=end-1;j++){
		if(a[j]<root){
			isRightValidate=false;
			break;
		}
	}
	//如果右边满足当前的根节点的话，则递归判断剩下的右边元素是不是满足 
	if(isRightValidate){
		isRightValidate= isValidate(a,seperator,end-1);
	}
	//只有左边和右边都满足了才返回true 
	return (isLeftValidate && isRightValidate) ;
	
}
int main(){
	

	int a[7]={5,7,6,9,11,10,8};
//	int a[4]={7,4,6,5};
	bool isRight=isValidate(a,0,7);
	if(isRight){
		cout<<"right"<<endl;
	}else{
		cout<<"wrong"<<endl;
	}
	return 0;
}