面試100題-06 判斷數(shù)組是否是查找二叉樹的輸入序列
一 問題描述：
該題目主要判讀輸入的數(shù)組，是否是查找樹的后序遍歷序列 ，比如一個數(shù)組 5,7,6,9,11,10,8就是一個數(shù)組序列
這就需要利用后序遍歷查找樹的一些性質 。
從頭開始掃描數(shù)組，當發(fā)現(xiàn)第一個位置i處，a[i]大于最后一個元素，則就有從i元素開始的每一個元素都大于尾部。
若發(fā)現(xiàn)不滿足上述定理，則證明該數(shù)組不是后序遍歷序列。
解決方法：
利用遞歸方法，首先確定遍歷數(shù)組，找出第一個大于尾部元素位置，即為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]) //若出現(xiàn)比尾部小的值，則返回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 ;
}