1. If n == 1, return [0].
2. Build adjacency list and degree array from edges.
3. Initialize queue with all nodes where degree == 1 (initial leaves).
4. Set remaining = n.
5. While remaining > 2:
a. size = queue.size()
b. remaining -= size
c. For each of the 'size' leaves dequeued:
- For each neighbor: decrement neighbor's degree
- If neighbor's degree becomes 1, enqueue it
6. Return all nodes remaining in the queue.題目描述: 給定一棵有 n 個節點(標號 0 到 n-1)的無向樹,選擇某個節點作為根,樹的高度為根到最遠葉節點的邊數。找出所有能使樹高度最小的根節點(稱為 MHT 根),答案至多 2 個。
關鍵洞察:「樹的中心」:
樹的最長路徑(直徑)唯一,MHT 的根必然落在直徑的中點,因此答案至多 2 個(直徑長為偶數時只有 1 個,奇數時有 2 個相鄰節點)。
演算法:從外向內逐層剝除葉節點:
類比拓撲排序(Topological Sort),將「度數為 1 的節點(葉節點)」視為最外層,不斷剝除,直到剩下 1 或 2 個節點為止——這些節點就是答案。
remaining = n,重複以下步驟直到 remaining <= 2:
size,remaining -= size。特殊情況: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⁴ 時勉強可接受,但效率低,面試中不建議作為主要解法。