网站建设市场趋势/电商平台推广方案

对于一个具有树特征的无向图，我们可选择任何一个节点作为根。图因此可以成为树，在所有可能的树中，具有最小高度的树被称为最小高度树。给出这样的一个图，写出一个函数找到所有的最小高度树并返回他们的根节点。

格式

该图包含 n 个节点，标记为 0 到 n - 1。给定数字 n 和一个无向边 edges 列表（每一个边都是一对标签）。

你可以假设没有重复的边会出现在 edges 中。由于所有的边都是无向边， [0, 1]和 [1, 0] 是相同的，因此不会同时出现在 edges 里。

示例 1:

输入: n = 4, edges = [[1, 0], [1, 2], [1, 3]]

        0
        |
        1
       / \
      2   3 

输出: [1]
示例 2:

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

     0  1  2
      \ | /
        3
        |
        4
        |
        5 

输出: [3, 4]
说明:

 根据树的定义，树是一个无向图，其中任何两个顶点只通过一条路径连接。 换句话说，一个任何没有简单环路的连通图都是一棵树。
树的高度是指根节点和叶子节点之间最长向下路径上边的数量。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-height-trees
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

package leetCodeTest;import java.util.*;public class 最小高度树 {public static void main(String[] args) {int[][] edges = new int[][]{{1, 0}, {1, 2}, {1, 3}};int n = 4;List<Integer> minHeightTrees = findMinHeightTrees(4, edges);System.out.println(minHeightTrees);}/*** 广度优先搜索+入度数组统计* 此类问题首先考虑广度优先搜索，最终的连接所有节点的最小高度树必然为入度最大的节点组成。* 所以首先需要得到节点的入度数组，然后记录每个节点的邻接节点数组map<Integer,List<Integer>>* 最后将这些节点分别入队（首先入队入度为一的节点），然后进行筛选。* 将队中节点分别拿出，并将与其相连的节点入度均减一（标识删除此节点）.* 然后判断是否有节点入度变为1，如果变为1则重新入队，继续执行上述操作，* 直到得到最后一组入度为一的节点数组即为最小高度树（因为剩下的节点是入度最大的节点，* 如果存在最小高度树必然存在这些节点）* @param n* @param edges* @return*/public static List<Integer> findMinHeightTrees(int n, int[][] edges) {ArrayList<Integer> res = new ArrayList();int i;//过滤特殊情况if (n<=2){for (i=0;i<n;i++){res.add(i);}return res;}int[] degree = new int[n];//记录节点的入度以及节点的邻接节点HashMap<Integer,ArrayList<Integer>> keymap = new HashMap();for (i=0;i<n;i++){keymap.put(i,new ArrayList());}for (int[] edge: edges){degree[edge[0]]++;degree[edge[1]]++;keymap.get(edge[0]).add(edge[1]);keymap.get(edge[1]).add(edge[0]);}//将入度为一的节点入队ArrayDeque<Integer> queue = new ArrayDeque();for (i=0;i<n;i++){if (degree[i] == 1)queue.offer(i);}while (!queue.isEmpty()){//刷新每次存储节点的数组用于存储新的数组res = new ArrayList<>();int size = queue.size();for (i=0;i<size;i++){int poll = queue.poll();res.add(poll);ArrayList<Integer> integers = keymap.get(poll);for (Integer integer: integers){degree[integer]--;if (degree[integer] == 1)queue.offer(integer);}}}return res;}
}