您好,登录后才能下订单哦!
这篇文章主要为大家展示了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个节点的时候停止循环。
1. 简单,只需理解基本的概念,就可以编写适合于各种情况的应用程序;2. 面向对象;3. 分布性,Java是面向网络的语言;4. 鲁棒性,java提供自动垃圾收集来进行内存管理,防止程序员在管理内存时容易产生的错误。;5. 安全性,用于网络、分布环境下的Java必须防止病毒的入侵。6. 体系结构中立,只要安装了Java运行时系统,就可在任意处理器上运行。7. 可移植性,Java可以方便地移植到网络上的不同机器。8.解释执行,Java解释器直接对Java字节码进行解释执行。
以上就是关于“java如何实现最小高度树”的内容,如果该文章对您有所帮助并觉得写得不错,劳请分享给您的好友一起学习新知识,若想了解更多相关知识内容,请多多关注亿速云行业资讯频道。
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。