java如何实现最小高度树

这篇文章主要为大家展示了java如何实现最小高度树，内容简而易懂，条理清晰，希望能够帮助大家解决疑惑，下面让小编带大家一起来研究并学习一下“java如何实现最小高度树”这篇文章吧。

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

格式

该图包含 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]

说明:

1，根据树的定义，树是一个无向图，其中任何两个顶点只通过一条路径连接。换句话说，一个任何没有简单环路的连通图都是一棵树。

2，树的高度是指根节点和叶子节点之间最长向下路径上边的数量。

答案：

 1public List<Integer> findMinHeightTrees(int n, int[][] edges) {
 2    if (n == 1)
 3        return Collections.singletonList(0);
 4    List<Set<Integer>> adj = new ArrayList<>(n);
 5    for (int i = 0; i < n; ++i)
 6        adj.add(new HashSet<>());
 7    for (int[] edge : edges) {
 8        adj.get(edge[0]).add(edge[1]);
 9        adj.get(edge[1]).add(edge[0]);
10    }
11    List<Integer> leaves = new ArrayList<>();
12    for (int i = 0; i < n; ++i)
13        if (adj.get(i).size() == 1)
14            leaves.add(i);
15    while (n > 2) {
16        n -= leaves.size();
17        List<Integer> newLeaves = new ArrayList<>();
18        for (int i : leaves) {
19            int j = adj.get(i).iterator().next();
20            adj.get(j).remove(i);
21            if (adj.get(j).size() == 1)
22                newLeaves.add(j);
23        }
24        leaves = newLeaves;
25    }
26    return leaves;
27}

解析：

这种解法比较简单，这里注意第19行，adj.get(i)获取的HashSet的size是等于1的。第20行会把叶子节点i给移除掉。我们先看个图更有助于理解

比如这个，他是不停的把叶子节点去掉，直到最后剩下一个或2个节点的时候停止循环。

Java的优点是什么

1. 简单，只需理解基本的概念，就可以编写适合于各种情况的应用程序；2. 面向对象；3. 分布性，Java是面向网络的语言；4. 鲁棒性，java提供自动垃圾收集来进行内存管理，防止程序员在管理内存时容易产生的错误。；5. 安全性，用于网络、分布环境下的Java必须防止病毒的入侵。6. 体系结构中立，只要安装了Java运行时系统，就可在任意处理器上运行。7. 可移植性，Java可以方便地移植到网络上的不同机器。8.解释执行，Java解释器直接对Java字节码进行解释执行。

以上就是关于“java如何实现最小高度树”的内容，如果该文章对您有所帮助并觉得写得不错，劳请分享给您的好友一起学习新知识，若想了解更多相关知识内容，请多多关注亿速云行业资讯频道。