題目連結：310. Minimum Height Trees
解題思路#
題目要我們尋找出最小高度樹（MHT），我一開始的想法是甚麼情況下樹的高度會最高？
答案是當樹的 root 剛好為樹的直徑中的兩端點之一時樹的高度會最高。
因此如果希望找到高度最矮的樹，那可以先找到樹的直徑，再把直徑路徑（path）的中點提起來當成樹的 root 就好了，這樣子樹的高度就會是 樹的直徑 / 2。
如果把直徑路徑中點以外的點提起來當成 root，那就會導致樹不平衡，一定會有一邊的高度 > 樹的直徑 / 2。
要注意的是如果直徑的長度為偶數的話，那麼答案就會有兩個（因為沒辦法剛好整除），如果是奇數的話答案就只會有一個。
程式碼#
Python#
class Solution:
def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
adj = [[] for _ in range(n)] # adjacency list
dis = [0] * n # distance
parent = {} # use to trace the path of diameter
def dfs(u, prev):
mx = u # farthest node
parent[u] = prev
for v in adj[u]:
if v == prev:
continue
dis[v] = dis[u] + 1
w = dfs(v, u)
if dis[w] > dis[mx]:
mx = w
return mx
for edge in edges:
adj[edge[0]].append(edge[1])
adj[edge[1]].append(edge[0])
# perform dfs twices to find diameter
start = dfs(0, -1)
end = dfs(start, -1)
# find the path of diameter
path = []
path.append(end)
while parent[end] != -1:
path.append(parent[end])
end = parent[end]
length = len(path)
if length & 1:
# odd
return [path[length >> 1]]
else:
# even
return [path[length >> 1], path[(length - 1) >> 1]]