摘要

樹是一種重要的數據結構，在許多應用里，我們希望選一個根，讓這棵樹的高度最小。LeetCode 310 就是這樣一道題：給你無向樹結構，選出所有可能成為“最小高度根”的節點。本文用 Swift 實現專業級解法，附上可運行代碼、過程圖解和復雜度分析，讓你從思路到實現完全掌握。這對理解中樞化圖結構、分層遍歷特別有幫助，既能用于面試，也有真實網絡或社交分析場景借鑒價值。

描述

題目定義：給定 n 個節點和 n–1 條無向邊，它構成一棵樹（連通且無環）。我們可以任選一個節點作為根，這樣就有一個高度；求所有能使樹高度最小的根節點。

幾個入門例子：

• n = 4, edges = [[1,0],[1,2],[1,3]]，根選 1 時高度是 1，是最小的，答案 [1]
• n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]，答案 [3,4]，兩者都是中心節點

這道題通過連續“剝離”葉子節點的辦法，能高效找到中心節點。

題解答案

func findMinHeightTrees(_ n: Int, _ edges: [[Int]]) -> [Int] {guard n > 1 else { return [0] }var adj = Array(repeating: [Int](), count: n)var degree = Array(repeating: 0, count: n)for e in edges {adj[e[0]].append(e[1])adj[e[1]].append(e[0])degree[e[0]] += 1degree[e[1]] += 1}var leaves = [Int]()for i in 0..<n where degree[i] == 1 {leaves.append(i)}var count = nwhile count > 2 {count -= leaves.countvar newLeaves = [Int]()for leaf in leaves {for nei in adj[leaf] {degree[nei] -= 1if degree[nei] == 1 { newLeaves.append(nei) }}}leaves = newLeaves}return leaves
}

這段代碼直接運行就可返回最小高度樹的所有根節點，非常簡潔。

題解代碼分析

思路來源：樹的“中心剝離法”

1. 從樹的葉子（度為 1）開始，逐層往內“剝離”節點。
2. 每剝掉一層葉子，就把剩余節點數減去。
3. 當剩下 ≤2 個節點時，它們就是樹的中心（中點），即所求根。

這個過程類似處理拓撲排序，復雜度優雅。

構造鄰接表和度數組

用 adj 存儲鄰居節點，degree 存儲當前節點的度數，初始準備葉子。

循環剝葉子

每次把當前所有葉子節點剝掉，并更新它們鄰居的度數；新的度為 1 的節點加入下一層葉子。

終止條件

剩余節點 ≤2 時，剝離結束。此時的 leaves 就是能成為最小高度樹根的集合。

示例測試及結果

print(findMinHeightTrees(4, [[1,0],[1,2],[1,3]])) // 輸出 [1]
print(findMinHeightTrees(6, [[3,0],[3,1],[3,2],[3,4],[5,4]])) // 輸出 [3,4]
print(findMinHeightTrees(1, [])) // 輸出 [0]
print(findMinHeightTrees(2, [[0,1]])) // 輸出 [0,1]

以上示例覆蓋了最小樹、單節點、雙節點等邊界情況，驗證結果都正確。

時間復雜度

• 構造圖和度數：O(n)
• 剝離所有葉子：每個節點最多被剝一次，邊最多處理一次，綜合 O(n)

所以整體時間復雜度是 O(n)，非常高效，適合 n ~2×10? 的場景。

空間復雜度

• 存圖結構 adj: O(n)
• 存度數數組 degree: O(n)
• 臨時葉子列表 leaves: O(n)（通常遠小于 n）

總體空間復雜度是 O(n)。

總結

• 算法核心是找到樹中心，通過 “多層剝葉” 思路解決，既直觀又高效。

• 使用場景：

  • 在圖論中求最短廣播源點
  • 網絡模塊尋找延遲最低的通信節點
  • 社交網絡中尋找信息傳播中樞

• Swift 實現簡潔明快，剝離過程邏輯清晰，適合算法面試與項目落地。