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

本文主要是介绍【LeetCode每日一题】310. 最小高度树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

- [310. 最小高度树](https://leetcode.cn/problems/minimum-height-trees/)
- - - - 思路：拓扑排序
      - 代码：

310. 最小高度树

思路：拓扑排序

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

代码：

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; // 返回最终结果列表}
}