Minimum Height Trees
For a undirected graph with tree characteristics, we can choose any node as the root. The result graph is then a rooted tree. Among all possible rooted trees, those with minimum height are called minimum height trees (MHTs). Given such a graph, write a function to find all the MHTs and return a list of their root labels.
Format
The graph contains n
nodes which are labeled from 0
to n - 1
. You will be given the number n
and a list of undirected edges
(each edge is a pair of labels).
You can assume that no duplicate edges will appear in edges
. Since all edges are undirected, [0, 1]
is the same as [1, 0]
and thus will not appear together in edges
.
Example 1:
Given n = 4
, edges = [[1, 0], [1, 2], [1, 3]]
0
|
1
/ \
2 3
return [1]
Example 2:
Given n = 6
, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]
0 1 2
\ | /
3
|
4
|
5
return [3, 4]
分析:
首先笨办法,假设每个点都是root, 然后利用BFS,看那个root到最后一个leaf的高度是多少,如果比目前找到的更小,则更新,如果相同,则把那个点加到list里。
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
List<Integer> all = new ArrayList<Integer>();
if (n <= ) {
all.add();
return all;
} Map<Integer, List<Integer>> map = new HashMap<>(); for (int i = ; i < n; i++) {
map.put(i, new ArrayList<Integer>());
} for (int[] edge : edges) {
map.get(edge[]).add(edge[]);
map.get(edge[]).add(edge[]);
} int minHeight = Integer.MAX_VALUE;
List<Integer> temp = new ArrayList<>();
for (int i = ; i < n; i++) {
int height = ;
boolean[] visited = new boolean[n];
visited[i] = true;
List<Integer> list = map.get(i);
while (list.size() != ) {
for (Integer k : list) {
if (!visited[k]) {
visited[k] = true;
temp.addAll(map.get(k));
}
}
list = temp;
temp = new ArrayList<>();
height++;
}
if (height < minHeight) {
all.clear();
all.add(i);
minHeight = height;
} else if (height == minHeight) {
all.add(i);
}
}
return all;
}
更好的方法,先构成一棵树,把数的叶子逐层的砍掉(叶子的degree为1),当这棵树只剩下2颗或者不到两颗的节点的时候,就停止。
public class Solution {
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
List<Integer> leaves = new ArrayList<Integer>();
if (n <= ) {
leaves.add();
return leaves;
} List<Set<Integer>> graph = new ArrayList<>(); for (int i = ; i < n; i++) {
graph.add(new HashSet<Integer>());
} for (int[] edge : edges) {
graph.get(edge[]).add(edge[]);
graph.get(edge[]).add(edge[]);
} for (int i = ; i < n; i++) {
if (graph.get(i).size() == ) {
leaves.add(i);
}
} while (n > ) {
n -= leaves.size();
List<Integer> newLeaves = new ArrayList<>();
for (int leave : leaves) {
for (int newLeaf : graph.get(leave)) {
graph.get(newLeaf).remove(leave);
if (graph.get(newLeaf).size() == ) {
newLeaves.add(newLeaf);
}
}
}
leaves = newLeaves;
} return leaves;
}
}
最新文章
- css3新属性object-fit,对页面img处理
- Linux系统中“动态库”和“静态库”那点事儿 /etc/ld.so.conf 动态库的后缀为*.so 静态库的后缀为 libxxx.a ldconfig 目录名
- sp.net2.0中的新增控件BulletedList的一些高级用法
- MVC强类型和弱类型的区别
- duilib\utils\utils.h(251) : error C2504: “VARIANT”: 未定义基类
- NIO中Selector分析
- windows下android开发环境搭建
- java实现DES算法
- 51单片机产生1Hz-5kHz可调占空比方波
- Javascript数组操作详细解答
- 如何在linux下使用git管理上传代码&;误删文件修复
- EF中防止sql注入
- python 关于文件的操作
- C#高级编程9 第18章 部署
- hover
- Eureka 集群高可用配置.
- python - 在Windows系统中安装Pygame及导入Eclipse
- Linux下查看Nginx的并发连接数和连接状态-乾颐堂
- Android(java)学习笔记118:BroadcastReceiver之 外拨电话的广播接收者
- sql 区分大小写查询