-
Notifications
You must be signed in to change notification settings - Fork 2
/
MinimumHeightTrees.java
94 lines (83 loc) · 2.97 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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
package Leetcode;
import java.util.*;
/**
* @author kalpak
*
* A tree is an undirected graph in which any two vertices are connected by exactly one path.
* In other words, any connected graph without simple cycles is a tree.
*
* Given a tree of n nodes labelled from 0 to n - 1, and an array of n - 1 edges where edges[i] = [ai, bi]
* indicates that there is an undirected edge between the two nodes ai and bi in the tree,
* you can choose any node of the tree as the root. When you select a node x as the root, the result tree has height h.
*
* Among all possible rooted trees, those with minimum height (i.e. min(h)) are called minimum height trees (MHTs).
*
* Return a list of all MHTs' root labels. You can return the answer in any order.
*
* The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.
*
* Example 1:
* Input: n = 4, edges = [[1,0],[1,2],[1,3]]
* Output: [1]
* Explanation: As shown, the height of the tree is 1 when the root is the node with label 1 which is the only MHT.
*
*
* Example 2:
* Input: n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]
* Output: [3,4]
*
*
* Example 3:
* Input: n = 1, edges = []
* Output: [0]
*
*
* Example 4:
* Input: n = 2, edges = [[0,1]]
* Output: [0,1]
*
*
* Constraints:
*
* 1 <= n <= 2 * 104
* edges.length == n - 1
* 0 <= ai, bi < n
* ai != bi
* All the pairs (ai, bi) are distinct.
* The given input is guaranteed to be a tree and there will be no repeated edges.
*/
public class MinimumHeightTrees {
public static List<Integer> findMinHeightTrees(int n, int[][] edges) {
if (n == 1)
return Collections.singletonList(0);
List<Set<Integer>> adjacencyList = new ArrayList<>(n);
for (int i = 0; i < n; ++i)
adjacencyList.add(new HashSet<>());
for (int[] edge : edges) {
adjacencyList.get(edge[0]).add(edge[1]);
adjacencyList.get(edge[1]).add(edge[0]);
}
List<Integer> leaves = new ArrayList<>();
for (int i = 0; i < n; ++i)
if (adjacencyList.get(i).size() == 1)
leaves.add(i);
while (n > 2) {
n -= leaves.size();
List<Integer> newLeaves = new ArrayList<>();
for (int i : leaves) {
int j = adjacencyList.get(i).iterator().next(); // Note that this is an iterator on the values of node_i
adjacencyList.get(j).remove(i); // Remove i from its connections
// Check if the connections become a leaf in itself
// If so, add them to the list for the next batch of traversal
if (adjacencyList.get(j).size() == 1)
newLeaves.add(j);
}
leaves = newLeaves;
}
return leaves;
}
public static void main(String[] args) {
int[][] edges = new int[][]{{3,0},{3,1},{3,2},{3,4},{5,4}};
System.out.println(findMinHeightTrees(6, edges));
}
}