面试100题-06 判断数组是否是查找二叉树的输入序列
一 问题描述：
该题目主要判读输入的数组，是否是查找树的后序遍历序列 ，比如一个数组 5,7,6,9,11,10,8就是一个数组序列
这就需要利用后序遍历查找树的一些性质 。
从头开始扫描数组，当发现第一个位置i处，a[i]大于最后一个元素，则就有从i元素开始的每一个元素都大于尾部。
若发现不满足上述定理，则证明该数组不是后序遍历序列。
解决方法：
利用递归方法，首先确定遍历数组，找出第一个大于尾部元素位置，即为i。然后从i开始扫描到尾部判读是否都比
尾部元素大。同理扫描1-i-1 元素，判断是否都比a[i]大。
使用了分治算法，用以解决该问题。
二 代码如下：
#include <iostream>
using namespace std ;
const int N = 7 ;
int a[N] =
{5 , 7 , 6 , 9 , 11 , 10 , 8};
bool judge(int l , int h)
{
if(l <= h)
{
int i , j ;
for(i = l ; i <= h ; i++)//很可能右子树或者左子树为空，考虑此种情况
{
if(a[i] >= a[h])
break ;
}
for(j = i ; j < h ;j++)
{
if(a[j] < a[h]) //若出现比尾部小的值，则返回false
return false ;
}
bool fl = true ;
if(l <= i - 1)
fl = judge(l, i - 1) ;
bool rl = true ;
if(i <= h - 1)
rl = judge(i , h -1) ;
return fl && rl ;
}
return false ;
}
int main()
{
bool f = judge(0 , N -1) ;
cout<<f<<endl ;
system("pause") ;
return 0 ;
}