本文共 1955 字，大约阅读时间需要 6 分钟。
如何找到使树高最小的顶点编号
在一个具有树性质的无向图中，树高是从根节点到叶子节点的最长路径的长度加一。我们的目标是找到使得树高最小的顶点编号。这个问题可以通过广度优先搜索（BFS）来解决，类似于剥洋葱的过程，从外层逐层向内剥，最后一层即为答案。
步骤解释：
特殊情况处理：如果图中只有一个顶点（n=1），则树高为1，顶点编号为0。
图的构建：使用邻接表表示图，并计算每个顶点的度数。邻接表通过哈希表实现，快速查找相邻顶点。
初始队列填充：将度数为1的顶点入队，因为这些顶点是叶子节点，可能作为根节点时树高最小。
BFS层序遍历：从队列中取出当前层的所有顶点，逐层扩展，记录每一层的顶点。每处理一个顶点，检查其相邻顶点，降低其度数。如果某个顶点的度数变为1，则将其加入下一层的队列中。
结果收集：当队列为空时，最后记录的顶点即为树高最小的根节点。所有属于最后一层的顶点都作为答案返回。
代码实现：
import java.util.*;public class Solution { public List findMinHeightTrees(int n, int[][] edges) { List res = new ArrayList<>(); if (n == 1) { res.add(0); return res; } Map > graph = buildGraph(edges); int[] degrees = getDegrees(n, edges); Queue queue = new LinkedList<>(); for (int i = 0; i < n; i++) { if (degrees[i] == 1) { queue.offer(i); } } while (!queue.isEmpty()) { res.clear(); int size = queue.size(); for (int i = 0; i < size; i++) { int cur = queue.poll(); res.add(cur); for (int next : graph.get(cur)) { degrees[next]--; if (degrees[next] == 1) { queue.offer(next); } } } } return res; } private int[] getDegrees(int n, int[][] edges) { int[] degrees = new int[n]; for (int[] edge : edges) { degrees[edge[0]]++; degrees[edge[1]]++; } return degrees; } private Map > buildGraph(int[][] edges) { Map > graph = new HashMap<>(); for (int[] edge : edges) { graph.computeIfAbsent(edge[0], k -> new HashSet<>()).add(edge[1]); graph.computeIfAbsent(edge[1], k -> new HashSet<>()).add(edge[0]); } return graph; }} 该算法的时间复杂度为O(n)，空间复杂度为O(n)。通过BFS层序遍历，我们能够高效地找到使树高最小的顶点编号。
转载地址：http://tgds.baihongyu.com/