題目
#

leetcode 310 - Minimum Height Trees (題目說明請點連結)

題目簡述
#

給定一個無向圖，找到所有可能的最小高度樹的根節點。最小高度樹是指以某個節點為根時，樹的高度最小。

範例
#

Example 1:

Input: n = 4, edges = [[1,0],[1,2],[1,3]]
Output: [1]
Explanation: 以節點 1 為根時，樹的高度為 1，這是所有可能根節點中的最小高度。

Example 2:

Input: n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]
Output: [3,4]
Explanation: 以節點 3 或 4 為根時，樹的高度為 2，這是所有可能根節點中的最小高度。

解題思路
#

這題要求我們找到無向圖中所有可能的最小高度樹的根節點。最小高度樹是指以某個節點為根時，樹的高度最小。

解法：拓撲排序（Topological Sort）

使用拓撲排序的思想，從葉子節點開始，逐層向內收縮。
維護每個節點的度數，將度數為 1的節點（葉子節點）加入隊列。
逐層移除葉子節點，直到剩餘節點數不超過 2。
剩餘的節點就是最小高度樹的根節點。

解法
#

最小高度樹的根節點一定是圖的"中心"節點
通過不斷移除葉子節點，最終剩下的節點就是中心節點
最多只會剩下 2 個節點（當圖是一條鏈時）

例子說明
#

n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]

graph TD; A[0] B[1] C[2] D[3] E[4] F[5] A --> D B --> D C --> D D --> E E --> F

構建圖和度數陣列

節點	度數	鄰居節點
0	1	[3]
1	1	[3]
2	1	[3]
3	4	[0,1,2,4]
4	2	[3,5]
5	1	[4]

接著逐步移除葉子節點

步驟	葉子節點	移除操作	剩餘節點	度數更新
初始化	[0,1,2,5]	-	[0,1,2,3,4,5]	度數：[1,1,1,4,2,1]
第 1 層	[0,1,2,5]	移除 0,1,2,5	[3,4]	節點3度數：4→1，節點4度數：2→1
第 2 層	[3,4]	停止移除	[3,4]	剩餘節點數 ≤ 2，停止

最終結果： [3, 4]

完整程式碼
#

java

import java.util.*;

class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        // 特殊情況：只有一個節點
        if (n == 1) {
            return Arrays.asList(0);
        }

        // 構建圖和度數陣列
        List<Set<Integer>> graph = new ArrayList<>();
        int[] degree = new int[n];

        // 初始化圖
        for (int i = 0; i < n; i++) {
            graph.add(new HashSet<>());
        }

        // 添加邊並計算度數
        for (int[] edge : edges) {
            int a = edge[0], b = edge[1];
            graph.get(a).add(b);
            graph.get(b).add(a);
            degree[a]++;
            degree[b]++;
        }

        // 將所有葉子節點（度數為1）加入隊列
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (degree[i] == 1) {
                queue.offer(i);
            }
        }

        // 逐層移除葉子節點，直到剩餘節點數不超過2
        while (n > 2) {
            int size = queue.size(); // 當前層的葉子節點數量
            n -= size; // 更新剩餘節點數

            // 處理當前層的所有葉子節點
            for (int i = 0; i < size; i++) {
                int leaf = queue.poll(); // 取出一個葉子節點
                
                // 獲取該葉子節點的所有鄰居
                List<Integer> toRemove = new ArrayList<>(graph.get(leaf));
                
                // 移除與鄰居的連接
                for (int neighbor : toRemove) {
                    graph.get(leaf).remove(neighbor);
                    graph.get(neighbor).remove(leaf);
                    degree[neighbor]--; // 鄰居的度數減1
                    
                    // 如果鄰居變成新的葉子節點，加入隊列
                    if (degree[neighbor] == 1) {
                        queue.offer(neighbor);
                    }
                }
            }
        }

        // 返回剩餘的節點作為最小高度樹的根節點
        return new ArrayList<>(queue);
    }
}