這題是用文字給出二元樹,檢查是否是完整的樹,如果是完整的樹即輸出廣度優先搜尋(BFS, Bread First Search)的結果。
我用的方法是用quicksort先對字串排序(eg, L, R, LL, LR, RL, RR,…),接著檢查是否是完整的樹,最後再照字串順序輸出該node的數字。Runtime 0.008,程式碼也相當龐大,在這題來說顯然有更快更精簡的方法,也許可以考慮使用struct, C++的STL函式庫,也許會有更好的表現。
CODE
#include <iostream> #include <string> #include <algorithm> using namespace std; #define MAX_LEN 300 #define MAX_NODE 256 int total, num[MAX_NODE], len[MAX_NODE]; char line[MAX_NODE][MAX_NODE]; bool rep; void sort_tree(int left, int right); bool isbigger(int a, int b); void swapnode(int a, int b); bool valid_tree(void); int main(){ char c, snum[MAX_LEN], sline[MAX_LEN]; int p, pnum, pline; int i; rep = false; total = 0; for(i=0; i<MAX_NODE; i++) num[i] = -1; while( (c = getchar()) != EOF ){ if( c == '(' ){ p = pnum = pline = 0; } else if( c == ')' ){ if( p == 0 ){ sort_tree(0, total-1); if( valid_tree() ){ cout << num[0]; for(i=1; i<total; i++) cout << ' ' << num[i]; cout << endl; } else cout << "not complete" << endl; //initialize rep = false; total = 0; for(i=0; i<MAX_NODE; i++) num[i] = -1; }//end of tree else{ if( pnum > 0 ){ snum[pnum] = '\0'; sscanf(snum, "%d", &num[total]); for(i=0; i<pline; i++) line[total][i] = sline[i]; line[total][pline] = '\0'; len[total] = pline; }//if pnum > 0 total++; }//end of node } else if( c == ',' ){ p++; } else if( c >= '0' && c <= '9' ){ snum[pnum++] = c; p++; } else if( c == 'L' || c == 'R' ){ sline[pline++] = c; p++; } else ; }//while return 0; } void sort_tree(int left, int right){ if( left < right ){ int i = left + 1; int j = right; while(1){ for(i; (isbigger(i, left)==false) && (i<=right); i++); for(j; (isbigger(j, left)==true) && (j>left); j--); if( i >= j ) break; swapnode(i, j); i++; j--; }//while swapnode(left, j); sort_tree(left, j-1); sort_tree(j+1, right); } } //return true if a > b, return false if a <= b bool isbigger(int a, int b){ if( a == b ) return false; if( len[a] > len[b] ) return true; if( len[a] < len[b] ) return false; for(int i=0; i<len[a]; i++){ if( line[a][i] > line[b][i] ) return true; else if( line[a][i] < line[b][i] ) return false; } rep = true; return false; } void swapnode(int a, int b){ swap(num[a], num[b]); swap(len[a], len[b]); char tmps[MAX_LEN]; strcpy(tmps, line[a]); strcpy(line[a], line[b]); strcpy(line[b], tmps); } bool valid_tree(void){ if( (num[0] == -1) || (len[0] != 0) ) return false; if( rep ) return false; int i, j; bool flag; char tmps[MAX_LEN]; for(i=1; len[i]<=1 && i<total; i++) if( num[i] == -1 ) return false; for(i; i<total; i++){ if( num[i] == -1 ) return false; flag = false; for(j=0; j<(len[i]-1); j++) tmps[j] = line[i][j]; tmps[j] = '\0'; for(j=(i-1); (j>=0) && (len[j]>=(len[i]-1)); j--) if( strcmp(line[j], tmps) == 0 ){ flag = true; break; } if( !flag ) return false; }//i return true; }
No comments:
Post a Comment