劍指OFFER之從二叉搜索樹的後序遍歷序列（九度OJ1367）

題目描述：

輸入一個整數數組，判斷該數組是不是某二叉搜索樹的後序遍歷的結果。如果是則輸出Yes,否則輸出No。假設輸入的數組的任意兩個數字都互不相同。

 

輸入：

每個測試案例包括2行：

第一行為1個整數n(1<=n<=10000)，表示數組的長度。

第二行包含n個整數，表示這個數組，數組中的數的范圍是[0,100000000]。

 

輸出：

對應每個測試案例，如果輸入數組是某二叉搜索樹的後序遍歷的結果輸出Yes，否則輸出No。

 

樣例輸入：

7
5 7 6 9 11 10 8
4
7 4 6 5

樣例輸出：

Yes
No

解題思路：

　　首先我們觀察題目：二叉搜索樹，後序遍歷兩個知識點。

　　二叉搜索樹，用於搜索，因此內部節點沒有重復的元素。另外，滿足二叉樹的性質，左子樹都比自己小，右子樹都比自己大。那麼可想而知，如果按照後序遍歷，先左後右最後自己的順序來遍歷樹，數組的最後一個元素肯定是自己（父節點），然後剩余的部分分成兩個部分，第一部分都比自己小（左子樹部分），第二部分都比自己大（右子樹部分），因此套用這個關系就可以循環檢驗出是否是二叉搜索樹的後序遍歷了。

int isPost(int i,int j){
    if(i == j)
        return 1;
    else{
        int k=j-1;
        while(k>=i){
            if(test[k] > test[j])
                k--;
            else
                break;
        }
        int flag = k;
        while(k>=i){
            if(test[k] < test[j])
                k--;
            else
                break;
        }
         
        if(k == i-1){
            if(test[i]>test[j] || test[j-1]<test[j] ){
                //printf("(%d-%d)\n",i,j-1);
                return isPost(i,j-1);
            }else{
                //printf("(%d-%d)(%d-%d)\n",i,flag,flag+1,j-1);
                return (isPost(i,flag))&&(isPost(flag+1,j-1));
            }
        }else{
            return 0;
        }
    }
}

　　另外要注意的是，本題的二叉樹並非滿二叉樹，因此可能出現下面的測試代碼：

3

1 2 3

也就是說，這個樹的父節點，只有左子樹，沒有右子樹（右孩子），但是這個測試用例仍然是要通過的。因此需要外加一個判斷，判斷是否僅有單個孩子子樹

 if(test[i]>test[j] || test[j-1]<test[j] ){
                //printf("(%d-%d)\n",i,j-1);
                return isPost(i,j-1);
            }

全部代碼：

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
int test[10005]={0};
int isPost(int i,int j);
int main(){
    int n,i;
    while(scanf("%d",&n)!=EOF){
        for(i=0;i<n;i++)
            scanf("%d",&test[i]);
        if(isPost(0,n-1))
            printf("Yes\n");
        else
            printf("No\n");
    }
    return 0;
}
int isPost(int i,int j){
    if(i == j)
        return 1;
    else{
        int k=j-1;
        while(k>=i){
            if(test[k] > test[j])
                k--;
            else
                break;
        }
        int flag = k;
        while(k>=i){
            if(test[k] < test[j])
                k--;
            else
                break;
        }
         
        if(k == i-1){
            if(test[i]>test[j] || test[j-1]<test[j] ){
                //printf("(%d-%d)\n",i,j-1);
                return isPost(i,j-1);
            }else{
                //printf("(%d-%d)(%d-%d)\n",i,flag,flag+1,j-1);
                return (isPost(i,flag))&&(isPost(flag+1,j-1));
            }
        }else{
            return 0;
        }
    }
}
/**************************************************************
    Problem: 1367
    User: xhalo
    Language: C
    Result: Accepted
    Time:10 ms
    Memory:952 kb
****************************************************************/