題目連結:
題目意譯:
一棵樹為一個無向圖,其中任意兩個節點以恰好一條路徑連接在一起。換句話說,任意一個沒有簡單環(Simple Cycles)的連通圖(Connected Graph)即是一棵樹。
給定有 n 個節點編號為 0 到 n - 1 的一棵樹,以及一個有著 n - 1 條邊的陣列 edges,其中 edges[i] = [ai, bi] 代表著 ai 和 bi 這兩個節點中有一條無向的邊,你可以選擇任意一個節點作為這棵樹的根節點。當你選擇一節點 x 作為根節點後,這棵樹將有著一樹高 h。在所有可能的有根樹(Rooted Trees)中,那些有著最小的樹高值(即,min(k))者,將被稱為最小高度樹(Minimum Height Trees,MHTs)。
回傳一個列表其包含著所有 MHTs 的根節點之編號。你可以按照任意順序回傳答案。
一棵有根樹的高度為從根節點到葉節點的路徑中最長的一條,其上面含有的邊數。
限制:
1 ≦ n ≦ 2 × 10 ^ 4
edges.length == n - 1
0 ≦ ai, bi < n
ai != bi
所有數對 (ai, bi) 皆相異。
輸入保證為一棵樹且沒有重邊的存在。
範例測資:
範例 1:
輸入: n = 4, edges = [[1,0],[1,2],[1,3]]
輸出: [1]
解釋: 如圖所示,當編號 1 作為根節點時的樹高為 1,且其為唯一的 MHT。
範例 2:
輸入: n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]
輸出: [3,4]
解題思維:
首先我們把輸入給定的陣列 edges 轉成一個鄰接表(Adjacency List),如
這題。接著我們便可以使用這個鄰接表來計算所有節點的度數(Degree),也就是其鄰居的個數。
緊接著,可以看到有根樹的葉節點是指那些度數為 1 的節點們。而這個定義也可以推廣到無根樹上。如下圖的無根樹中,紅色圈圈外側即是葉節點們:
再以上圖為例,可以看到這些葉節點作為根節點時,其樹高不可能是最小的。因為我們如果把某個葉節點當作根節點的話,可以看到決定其樹高的路徑必定「走進」紅色圈圈內,再「走出」紅色圈圈外;而如果我們挑紅色圈圈內的節點作為根節點的話,可以看到我們只需「走出」紅色圈圈外。而「走進」+「走出」的路徑長度明顯大於只有「走出」的路徑長度。
因此我們可以無視掉這些節點,讓上圖變為如下:
此時,可以看到同樣的論述可以再度使用一次。因此上圖變為下圖:
這時,可以看到整棵樹只剩下了葉節點(也就是不存在紅色圈圈來框住「內部」的節點)。因此我們便可以知道這兩個節點即是可以在原本的樹得到 MHTs 的兩個節點。
而其他的樹也可以做出類似的事情,來刪到只剩下葉節點,最後剩下的節點即是所求。而這個「刪除」的動作實際上跟拓樸排序(Topological Sort)相當地類似,參見
這題。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。