回分類題庫
d005: 99年台中區第五題
關鍵字: 99年台中區複賽

測資點 : 2 | Time Limit : 1000 ms | Memory Limit : 32000 KB
Accepted : 88 Times / 78 Users | Submit : 221 Times / 79 Users | Accepted rate : 99%
題目加入時間 : 2011-09-08 10:22

Content: 简体中文

給定一節點(node)內容為整數的二元數(binary tree),請寫一程式決定該二元樹中由樹根(root)走到樹葉(leaf)節點所經過的節點其數值總和最大者其值為何?例如以下的這一棵二元樹共有四 條由樹根到樹葉節點的路徑,其長度分別為36=4+11+8+13, 47=4+11+32, 34=4+9+7+14及21=4+9+7+1,因此答案為47。

二元樹在檔案內的表示格式如下所示(以遞迴方式作定義):
empty binary tree ::= ()    /* 空的二元樹表示法為() */
binary_tree ::= empty binary tree | (integer binary_tree binary_tree)  
/*一棵二元樹可以是一棵空的二元樹或者是一個整數節點底下有左右兩棵二元樹 */

值得一提的是所有樹葉節點的形式都是以(integer () () )的形式出現;例如樹葉節點13以(13 ()())表示,樹葉節點14以(14 ()())表示。以上圖為例,以節點8為樹根的子樹其表示法為 (8 (13 () ()) ())。以節點7為樹根的子樹其表示法為 (7(14 () ())(1 () ()))。該二元樹圖在檔案內的表示式是 (4 (11 (8(13()()) ()) (32 () ())) (9() (7(14 () ())(1 () ())) ))。

本程式輸入資料第一列的值 k (1<=k<=10)代表有幾組測試資料,第二列開始就是如上所述的二元樹的表示式,所有的二元樹的表示式都是正確的而且有可能跨越好幾列。輸出的內容只要說明第幾棵二元樹其最長路徑總和為多少便可。

Input:

第一行先輸入一個整數 k,代表之後有幾組測試資料,接下來則是這 k 組二元樹的定義,每組資料可能跨越好幾列。

Output:

請依照下面的輸出範例,輸出第幾棵二元樹最長路徑長度為多少。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
3
(5(4(11(7()())(2()()))()) (8(13()())(4()(1()()))))
(4 (11 (8 (13 () ()) ()) (32 () ())) (9()(7(14 () ())(1 () ()))))
(3 
       (2 (4 () () )  (8 () () ) )
       (1 (6 () () )  (4 () () ) ) )

Sample Output :

第一棵二元樹最長路徑長度:27
第二棵二元樹最長路徑長度:47
第三棵二元樹最長路徑長度:13

Hint :

Author :

99年台中區複賽 (管理員:sagit)

  Solve it!   Status Forum