-
Notifications
You must be signed in to change notification settings - Fork 1
/
MinimumHeightTrees.java
69 lines (63 loc) · 1.85 KB
/
MinimumHeightTrees.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
package com.hncboy;
import java.util.*;
/**
* @author hncboy
* @date 2022/4/6 12:25
* 310.最小高度树 TODO
*/
public class MinimumHeightTrees {
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
List<Integer> ans = new ArrayList<Integer>();
if (n == 1) {
ans.add(0);
return ans;
}
List<Integer>[] adj = new List[n];
for (int i = 0; i < n; i++) {
adj[i] = new ArrayList<Integer>();
}
for (int[] edge : edges) {
adj[edge[0]].add(edge[1]);
adj[edge[1]].add(edge[0]);
}
int[] parent = new int[n];
Arrays.fill(parent, -1);
/* 找到与节点 0 最远的节点 x */
int x = findLongestNode(0, parent, adj);
/* 找到与节点 x 最远的节点 y */
int y = findLongestNode(x, parent, adj);
/* 求出节点 x 到节点 y 的路径 */
List<Integer> path = new ArrayList<Integer>();
parent[x] = -1;
while (y != -1) {
path.add(y);
y = parent[y];
}
int m = path.size();
if (m % 2 == 0) {
ans.add(path.get(m / 2 - 1));
}
ans.add(path.get(m / 2));
return ans;
}
public int findLongestNode(int u, int[] parent, List<Integer>[] adj) {
int n = adj.length;
Queue<Integer> queue = new ArrayDeque<>();
boolean[] visit = new boolean[n];
queue.offer(u);
visit[u] = true;
int node = -1;
while (!queue.isEmpty()) {
int curr = queue.poll();
node = curr;
for (int v : adj[curr]) {
if (!visit[v]) {
visit[v] = true;
parent[v] = curr;
queue.offer(v);
}
}
}
return node;
}
}