c101-acm-122 - Trees on the level

在本問題中，二元樹以節點來表示。每個節點以一對(n,s)來表示。n代表此節點的值，s為一字串，代表從根節點到達此 節點的路徑。其中L代表往左，R代表往右。所以在上方的圖中內容為13的節點其表示法為(13,RL)，而內容為2的節點其表示法為(2,LLR)，而根 節點為(5,)。

輸入說明 ：

輸入含有多組測試資料。每組測試資料為若干節點的集合。各節點間以white space（包含空白、換列等字元）分隔。注意：在各節點內（也就是左刮號到又刮號之間）不會有white space。當遇到一()的節點，代表該組測試資料結束。請參考Sample Input。

輸出說明 ：

對每一組測試資料，如果輸入的節點可以正常的構成一二元樹的話，請輸出按「階層」走訪的結果。如果輸入的節點無法正常的構成一二元樹的話，也就是說有某些該有的節點沒有給，或重複給（同一路徑有2個節點），請輸出not complete。請參考Sample Output。

範例輸入 ：

(11,LL) (7,LLL) (8,R)

(5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) ()

(3,L) (4,R) ()

(11,LL) (7,LLL) (2,LLL) (8,R)

(5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) ()

範例輸出 ：

5 4 8 11 13 4 7 2 1

not complete

not complete

提示 ：

* 中文翻譯：Lucky 貓

出處 ：

ACM 122

解題策略

建立樹，使用queue實作level order走訪