310. 最小高度樹

樹是一個無向圖，其中任何兩個頂點隻通過一條路徑連接配接。 換句話說，一個任何沒有簡單環路的連通圖都是一棵樹。

給你一棵包含 n 個節點的樹，标記為 0 到 n - 1 。給定數字 n 和一個有 n - 1 條無向邊的 edges 清單（每一個邊都是一對标簽），其中 edges[i] = [ai, bi] 表示樹中節點 ai 和 bi 之間存在一條無向邊。

可選擇樹中任何一個節點作為根。當選擇節點 x 作為根節點時，設結果樹的高度為 h 。在所有可能的樹中，具有最小高度的樹（即，min(h)）被稱為 最小高度樹 。

請你找到所有的 最小高度樹 并按 任意順序 傳回它們的根節點标簽清單。

樹的 高度 是指根節點和葉子節點之間最長向下路徑上邊的數量。

來源：力扣（LeetCode）

連結：https://leetcode-cn.com/problems/minimum-height-trees

著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

import java.util.*;

class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        if (n == 1) {
            return Collections.singletonList(0);
        }
        List<Integer> ans = new ArrayList<>();
        int[] in = new int[n];
        Map<Integer, Set<Integer>> graph = new HashMap<>();
        for (int[] edge : edges) {
            in[edge[0]]++;
            in[edge[1]]++;
            graph.computeIfAbsent(edge[0], k -> new HashSet<>()).add(edge[1]);
            graph.computeIfAbsent(edge[1], k -> new HashSet<>()).add(edge[0]);
        }
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < in.length; ++i) {
            if (in[i] == 1) {
                queue.offer(i);
            }
        }

        while (!queue.isEmpty()) {
            ans = new ArrayList<>();
            int size = queue.size();
            while (size-- > 0) {
                Integer node = queue.poll();
                ans.add(node);
                Set<Integer> tos = graph.getOrDefault(node, Collections.emptySet());
                for (int to : tos) {
                    if (--in[to] == 1) {
                        queue.offer(to);
                    }
                }
            }
        }

        return ans;
    }
}
           

心之所向，素履以往 生如逆旅，一葦以航