輸入一個整數數組，判斷該數組是不是某二叉搜索樹的後序遍歷的結果。如果是則輸出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 代碼AC： 思想：需要遍歷樹，二叉排序樹的特點是 lchild.key < root.key < rchild.key 那麼我們使用分治思想，先利用上面特點將左右子樹分開，遇到第一個大於root.key的之後(右邊)就是又子樹，那麼當我們在遍歷又子樹的時候如果遇到小於root.key的情況，那麼就是錯誤的序列。。。。 [cpp] // 使用分治！ #include <stdio.h> #include <stdlib.h> long int *num; int fun( long int low, long int high ) { long int i, l, tmp_idx, flag = 1; if( low >= high ) { return 1; } for( i = low; i < high , num[i] < num[high]; i++ ); tmp_idx = i; for( i; i < high; i++ ) { if( num[i] < num[high] ) { return 0; } } if( fun( low, tmp_idx - 1 ) == 0 ) { return 0; } if( fun( tmp_idx + 1, high ) == 0 ) { return 0; } return 1; } int main() { long int n, i, low, high; while( scanf("%ld", &n) != EOF ) { num = ( long int* )malloc( sizeof( long int ) * n ); for( i = 0; i < n; i++ ) { scanf("%ld", &num[i]); } www.2cto.com if( fun( 0, n - 1 ) ) { printf("Yes\n"); } else { printf("No\n"); } free( num ); } return 0; }
