演算法中階・樹的走訪
父子清單建樹:逐層走訪、深度優先找路徑成本、沿父指標找最近共同祖先。
這一頁是題幹試閱;登入/註冊後每題可以在瀏覽器裡執行、對答案,第一次交對 +10 XP。
- 01
設定版本樹逐層列出
中等樹設定檔的每個版本都從某個父版本衍生出來,形成一棵樹(只有一個根版本)。檔案以「版本 父版本」逐行記錄,根版本的父版本寫
-。請從根開始一層一層列出所有版本,並找出版本最多的那一層。同一個父版本底下的子版本,依它們在輸入中出現的先後排列;每一層依「上一層的順序,再依各自子版本的順序」排列。
輸入:
第 1 行:組數 t
每組:第 1 行是版本數 n,接下來 n 行是
版本 父版本輸出:每組
- 每一層一行:
深度: 版本 版本 ...(根的深度是 0,深度與冒號之間沒有空白,冒號後一個空白) - 最後一行:
widest 深度 個數,個數相同時取深度較小的
要求:先建「父版本 → 子版本 list」的 dict,再用佇列一層一層走(每輪把目前這一層全部處理完再進下一層)。
範例輸入:
1
4
b a
a -
c a
d b
範例輸出:
0: a
1: b c
2: d
widest 1 2
類型對應:LeetCode「N-ary Tree Level Order Traversal」類(情境與敘述為本平台改寫)。
輸入請用 input() 逐行讀取(平台不支援 sys.stdin)。執行時平台會把每一行測資回顯在輸出最前面,這是正常的,不用自己印。starter 已先把全部輸入讀進來,請保留這段,不要在迴圈裡邊讀邊印(回顯行會插進輸出中間,就對不上答案)。本題在瀏覽器內以 Pyodide 執行,只用標準函式庫。
作答登入後可作答 - 每一層一行:
- 02
血緣路徑成本剛好等於預算
中等樹資料血緣是一棵樹:根是原始資料的匯入步驟,每往下一層是一個處理步驟,每個步驟有處理成本。從根走到某個葉節點(沒有子節點的步驟)就是一條完整產出的路徑,路徑成本是路上所有步驟(含根與葉)的成本總和。給幾個預算值,列出成本剛好等於預算的所有路徑。
同一個父步驟底下的子步驟,依它們在輸入中出現的先後排列;路徑依「從根開始深度優先、先走前面的子步驟」的順序列出。
輸入:
第 1 行:步驟數 n
接下來 n 行:
步驟 父步驟 成本(根的父步驟寫-,成本是非負整數;父步驟可能在子步驟之後才出現)最後一行:預算值(整數,以空白分隔,至少一個)
輸出:每個預算依輸入順序
- 先印一行
預算 k,k 是符合的路徑數 - 接下來 k 行,每行一條路徑,步驟以
>連接
要求:用深度優先走訪,一路帶著目前的路徑與累計成本,走到葉節點才判斷;不要先把所有路徑存起來。
範例輸入:
4
load - 1
a load 2
b load 3
c a 1
4 3
範例輸出:
4 2
load > a > c
load > b
3 0
類型對應:LeetCode「Path Sum II」類(情境與敘述為本平台改寫)。
輸入請用 input() 逐行讀取(平台不支援 sys.stdin)。執行時平台會把每一行測資回顯在輸出最前面,這是正常的,不用自己印。starter 已先把全部輸入讀進來,請保留這段,不要在迴圈裡邊讀邊印(回顯行會插進輸出中間,就對不上答案)。本題在瀏覽器內以 Pyodide 執行,只用標準函式庫。
作答登入後可作答 - 先印一行
- 03
兩個設定版本的共同祖先
中等樹設定檔的版本樹裡,每個版本記著它的父版本(根版本的父版本寫
-)。合併兩個分支前,要找出兩個版本最近的共同祖先:同時是兩者祖先、而且離它們最近的版本。一個版本也算是自己的祖先。輸入:
第 1 行:版本數 n
接下來 n 行:
版本 父版本下一行:查詢數 q
接下來 q 行:
版本a 版本b輸出:每個查詢一行
共同祖先 a往上幾步 b往上幾步(步數是從該版本沿父版本往上走到共同祖先的次數)。要求:用父版本指標往上走,不需要建子節點清單。
範例輸入:
4
r -
a r
b r
c a
2
c b
a c
範例輸出:
r 2 1
a 0 1
類型對應:LeetCode「Lowest Common Ancestor of a Binary Tree III」類(情境與敘述為本平台改寫)。
輸入請用 input() 逐行讀取(平台不支援 sys.stdin)。執行時平台會把每一行測資回顯在輸出最前面,這是正常的,不用自己印。starter 已先把全部輸入讀進來,請保留這段,不要在迴圈裡邊讀邊印(回顯行會插進輸出中間,就對不上答案)。本題在瀏覽器內以 Pyodide 執行,只用標準函式庫。
作答登入後可作答

送件鴿飛出去了