題目

https://leetcode.com/problems/minimum-height-trees/#/description

分析

題目的要求是在一個沒有環(huán)的圖里，找一個節(jié)點(diǎn)作為根節(jié)點(diǎn)，將圖轉(zhuǎn)換成一棵樹，使樹的高度最小
先考慮最簡單的圖，每個節(jié)點(diǎn)只有一條邊進(jìn)入和一條邊離開，這樣的圖退化成為一個鏈表。選取某一個節(jié)點(diǎn)作為Root時，樹的高度由根節(jié)點(diǎn)到左右兩側(cè)葉子節(jié)點(diǎn)的最大路徑?jīng)Q定。因此想要樹的高度最小，需要左右兩側(cè)的路徑大小盡可能接近。對于鏈表來說，中間節(jié)點(diǎn)就是我們的尋找的根節(jié)點(diǎn)，根據(jù)全部節(jié)點(diǎn)的個數(shù)不同，符合條件的根節(jié)點(diǎn)可能是一個或者兩個。尋找中間節(jié)點(diǎn)的算法很簡單，可以分別從左右兩個葉子節(jié)點(diǎn)以相同的速度前進(jìn)，相遇的節(jié)點(diǎn)即是中間節(jié)點(diǎn)。

退化成鏈表的圖

回到題目中的場景：沒有環(huán)的圖，可以看作是多條鏈表，并且共用了一些節(jié)點(diǎn)。可以看出樹的高度是由最長的鏈表決定的，即圖中1-7的鏈表。尋找MHT根節(jié)點(diǎn)問題就轉(zhuǎn)化成了找到最長的鏈表的中間節(jié)點(diǎn)

沒有環(huán)的圖

算法

獲取所有葉子節(jié)點(diǎn)
while true
     從所有葉子節(jié)點(diǎn)出發(fā)，當(dāng)前節(jié)點(diǎn)為葉子節(jié)點(diǎn)的下一個節(jié)點(diǎn)
     刪除所有葉子節(jié)點(diǎn)
     當(dāng)前節(jié)點(diǎn)是否變?yōu)槿~子節(jié)點(diǎn)？
        是：當(dāng)前節(jié)點(diǎn)加入葉子節(jié)點(diǎn)
        否：表示有更長的路徑，舍棄掉此路徑
     葉子節(jié)點(diǎn)數(shù)量 <= 2
        使用鏈表中間節(jié)點(diǎn)算法找到根節(jié)點(diǎn)，結(jié)束   

實(shí)現(xiàn)代碼