面試100題-06 判斷數(shù)組是否是查找二叉樹(shù)的輸入序列
一 問(wèn)題描述：
該題目主要判讀輸入的數(shù)組，是否是查找樹(shù)的后序遍歷序列 ，比如一個(gè)數(shù)組 5,7,6,9,11,10,8就是一個(gè)數(shù)組序列
這就需要利用后序遍歷查找樹(shù)的一些性質(zhì) 。
從頭開(kāi)始掃描數(shù)組，當(dāng)發(fā)現(xiàn)第一個(gè)位置i處，a[i]大于最后一個(gè)元素，則就有從i元素開(kāi)始的每一個(gè)元素都大于尾部。
若發(fā)現(xiàn)不滿足上述定理，則證明該數(shù)組不是后序遍歷序列。
解決方法：
利用遞歸方法，首先確定遍歷數(shù)組，找出第一個(gè)大于尾部元素位置，即為i。然后從i開(kāi)始掃描到尾部判讀是否都比
尾部元素大。同理掃描1-i-1 元素，判斷是否都比a[i]大。
使用了分治算法，用以解決該問(wèn)題。
二 代碼如下：
#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++)//很可能右子樹(shù)或者左子樹(shù)為空，考慮此種情況
{
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 ;
}