310. Minimum Height Trees

Minimum Height Trees

題目描述： 給定一棵有 n 個節點（標號 0 到 n-1）的無向樹，選擇某個節點作為根，樹的高度為根到最遠葉節點的邊數。找出所有能使樹高度最小的根節點（稱為 MHT 根），答案至多 2 個。

關鍵洞察：「樹的中心」：

樹的最長路徑（直徑）唯一，MHT 的根必然落在直徑的中點，因此答案至多 2 個（直徑長為偶數時只有 1 個，奇數時有 2 個相鄰節點）。

演算法：從外向內逐層剝除葉節點：

類比拓撲排序（Topological Sort），將「度數為 1 的節點（葉節點）」視為最外層，不斷剝除，直到剩下 1 或 2 個節點為止——這些節點就是答案。

1. 建立鄰接表與每個節點的度數（degree）。
2. 將所有初始葉節點（degree = 1）加入佇列。
3. remaining = n，重複以下步驟直到 remaining <= 2：
   • 計算這一輪葉節點的數量 size，remaining -= size。
   • 彈出這一輪所有葉節點，將其鄰居的 degree 各減 1；若鄰居 degree 降為 1，加入佇列（成為下一輪葉）。
4. 佇列中剩下的節點即為答案。

特殊情況：n = 1 時直接回傳 {0}（單節點無邊）。

時間複雜度：O(n) — 建圖 O(n)；每個節點最多被加入佇列一次、被彈出一次，每條邊被遍歷兩次，總計 O(n + n-1) = O(n)。

空間複雜度：O(n) — 鄰接表、degree 陣列、佇列各佔 O(n) 空間。

雙 DFS 找直徑中心 O(n)：第一次 DFS 從任意節點出發，找到最遠節點 u；第二次 DFS 從 u 出發，找到最遠節點 v；u-v 路徑即為直徑，取中間 1 或 2 個節點為答案。邏輯等價但需要記錄路徑，實作略複雜。

暴力法 O(n²)：對每個節點做一次 DFS/BFS 求樹高，取最小值。n ≤ 2×10⁴ 時勉強可接受，但效率低，面試中不建議作為主要解法。

1. 本題的「葉剝除」與有向圖中的 Kahn's Algorithm（拓撲排序）有何相似之處？在有向圖中，「入度為 0 的節點」對應本題中的哪個概念？
2. 如果樹的節點數 n 非常大（如 10⁸），但邊的數量有限（稀疏圖），上述 O(n) 解法在空間上有何挑戰？如何優化？
3. 本題保證答案至多 2 個根節點。你能從「樹的直徑唯一性」出發，用數學方式說明為什麼不可能有 3 個或以上的 MHT 根？