05 August 2008
树的直径是该树中最长路径中的边数。
有一棵由 n 个节点标记为 0 到 n - 1 的无向树。给定一个二维数组边缘，其中 edges.length == n - 1 和 edges[i] = [ai, bi] 表示存在无向边在树中的节点 ai 和 bi 之间。
返回树的直径。
DFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public int treeDiameter(int[][] edges) {
Map<Integer, List<Integer>> map = new HashMap<>();
for (int[] e : edges){
map.computeIfAbsent(e[0], o -> new ArrayList<>()).add(e[1]);
map.computeIfAbsent(e[1], o -> new ArrayList<>()).add(e[0]);
}
//2 DFS. -- here because we are counting the num of nodes, and the ans should be num of node - 1
return --dfs(map, dfs(map, 0, -1)[1], -1)[0];
}
//return new int[]{max distance, the farthest node}
private int[] dfs(Map<Integer, List<Integer>> map, int idx, int parent){
int[] max = new int[2];
if (map.get(idx).size() == 1) max[1] = idx; //deadend, put the node in
for (int next : map.get(idx)){
if (next == parent) continue; //can't go back!
int[] res = dfs(map, next, idx);
if (res[0] > max[0]) max = res;
}
max[0]++;
return max;
}
}
BFS
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
class Solution {
int steps;
public int treeDiameter(int[][] edges) {
Map<Integer, List<Integer>> map = new HashMap<>();
for (int[] edge : edges) {
map.putIfAbsent(edge[0], new ArrayList<>());
map.putIfAbsent(edge[1], new ArrayList<>());
map.get(edge[0]).add(edge[1]);
map.get(edge[1]).add(edge[0]);
}
getdeepestNode(map, getdeepestNode(map, 0));
return steps - 1;
}
private int getdeepestNode(Map<Integer, List<Integer>> map, int node) {
steps = 0;
Queue<Integer> queue = new ArrayDeque<>();
queue.offer(node);
Set<Integer> visited = new HashSet<>();
visited.add(node);
int deepestNode = node;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
int poll = queue.poll();
deepestNode = poll;
if (map.containsKey(poll)) {
for (int neighbor : map.get(poll)) {
if (!visited.contains(neighbor)) {
visited.add(neighbor);
queue.offer(neighbor);
}
}
}
}
steps++;
}
return deepestNode;
}
}