【LeetCode每日一题】310. 最小高度树

310. 最小高度树

思路：拓扑排序

1. 首先判断节点数量n，如果只有一个节点，则直接返回该节点作为最小高度树的根节点。
2. 构建邻接表g和度数数组degree：
   • 使用邻接表g存储每个节点的相邻节点。
   • 使用度数数组degree存储每个节点的度数（即相邻节点的数量）。
3. 遍历边数组edges，构建邻接表g和更新度数数组degree：
   • 对于每条边[e[0], e[1]]，将节点e[0]与节点e[1]互相添加到各自的邻接表中，同时更新它们的度数。
4. 初始化队列q，并将所有叶子节点（度数为1的节点）加入队列：
   • 遍历所有节点，将度数为1的节点加入队列q。
5. 使用BFS遍历叶子节点层级，不断更新度数并将新的叶子节点加入队列：
   • 从队列中取出当前层级的叶子节点，更新其相邻节点的度数。
   • 若相邻节点的度数更新为1，则将其加入队列q。
6. 最终队列中剩下的节点即为最小高度树的根节点列表，将其返回作为结果。

代码：

class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        // 如果只有一个节点，直接返回该节点
        if (n == 1) {
            return List.of(0);
        }

        // 构建邻接表
        List<Integer>[] g = new List[n];
        Arrays.setAll(g, k -> new ArrayList<>());
        int[] degree = new int[n]; // 存储每个节点的度数
        for (int[] e : edges) {
            int a = e[0], b = e[1];
            g[a].add(b);
            g[b].add(a);
            ++degree[a];
            ++degree[b];
        }

        Deque<Integer> q = new ArrayDeque<>();
        // 将所有叶子节点（度数为1）加入队列
        for (int i = 0; i < n; ++i) {
            if (degree[i] == 1) {
                q.offer(i);
            }
        }

        List<Integer> ans = new ArrayList<>();
        while (!q.isEmpty()) {
            ans.clear(); // 清空结果列表
            // 遍历当前层的节点
            for (int i = q.size(); i > 0; --i) {
                int a = q.poll();
                ans.add(a); // 将当前节点加入结果列表
                // 更新与当前节点相邻的节点的度数
                for (int b : g[a]) {
                    if (--degree[b] == 1) {
                        q.offer(b); // 若更新后度数为1，则加入队列
                    }
                }
            }
        }
        return ans; // 返回最终结果列表
    }
}

点击移步博客主页，欢迎光临~