微軟等數據結構與算法面試100題 第九題

第九題
判斷整數序列是不是二元查找樹的後序遍歷結果
題目：輸入一個整數數組，判斷該數組是不是某二元查找樹的後序遍歷的結果。
如果是返回true，否則返回false。
例如輸入5、7、6、9、11、10、8，由於這一整數序列是如下樹的後序遍歷結果：
         8
      /  \
     6    10
    / \  / \
   5  7 9  11
因此返回true。
如果輸入7、4、6、5，沒有哪棵樹的後序遍歷的結果是這個序列，因此返回false。

分析：
本題目是考察後序遍歷二叉搜索樹的性質，即右子樹大於根節點大於左子樹，因此可以遞歸使用這個性質作為判定。

首選整個樹的根節點在序列末尾，然後確定去左子樹和右子樹是否滿足上面的性質，在這裡需要指出的是，可以不用判定右子樹是否大於根節點，因為右子樹再進行拆分判定的時候又可以分為判定左右子樹，因此可以不用判定右子樹而只判定左子樹。
遞歸程序的出口即為判定的序列長度為2和3時，即只有左子樹和根節點、左子樹右子樹和根節點兩種情況，針對這兩種情況分別寫出判定方法和返回值。

代碼：
[cpp] 
#include<iostream> 
 
using namespace std; 
 
  
bool CheckSeqBSTree(int * sequence, int startIndex ,int length) 
{ 
    if(NULL==sequence||length==0) 
        return false; 
    //找到左右子樹的分割符 
    int i = startIndex; 
    int leftLength = 0; 
    int rightLength = 0; 
 
    for(; i < startIndex + length -1 ; i++, leftLength++) 
    { 
        if(sequence[i]>sequence[startIndex+length-1]) 
            break;       
    } 
     
    rightLength = length - leftLength - 1; 
 
    //說明：其實右子樹可以不用判斷的 因為每次把右子樹都會再繼續拆分成左右子樹，只判斷左子樹具有完備性 
    bool BSTree = false; 
    //check後面的點是否大於 
     
    //for(; i < length -1 ; i++) 
    //{ 
    //  if(sequence[i]<sequence[length-1]) 
    //      BSTree = false; 
 
    //} 
     
    //遞歸程序出口 
    if(length==2) 
    { 
        if(sequence[startIndex]<sequence[startIndex+1]) 
            BSTree = true; 
    } 
    else if (length==3) 
    { 
        if(sequence[startIndex]<sequence[startIndex+2]&&sequence[startIndex+1]>sequence[startIndex+2]) 
            BSTree = true; 
    } 
    else 
    { 
        BSTree= CheckSeqBSTree(sequence,startIndex,leftLength) && CheckSeqBSTree(sequence,i,rightLength); 
    } 
     
 
    return BSTree; 
} 
int main() 
{ 
 
    int a[] = {5, 7, 6,9, 11, 10, 8}; 
 
 
    cout<<CheckSeqBSTree(a,0,7); 
 
    return 0; 
}