[LeetCode] Problem 310 - Minimum Height Trees

Posted on | In ,

For an 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

No.1

Input: n = 4, edges = [[1, 0], [1, 2], [1, 3]]

1
2
3
4
5
  0
  |
  1
 / \
2   3

Output: [1]

No.2

Input: n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]

1
2
3
4
5
6
7
0  1  2
 \ | /
   3
   |
   4
   |
   5

Output: [3, 4]

Note

  • According to the definition of tree on Wikipedia: “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.”
  • The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.

Code

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
public List<Integer> findMinHeightTrees(int n, int[][] edges) {        
    List<Integer> result = new ArrayList<>();
    
    if (n == 1) {
        result.add(0);
        return result;
    }
    
    List[] adj = new ArrayList[n];

    for (int i = 0; i < n; i++)
        adj[i] = new ArrayList<Integer>();

    for (int i = 0; i < edges.length; i++) {
        int v1 = edges[i][0];
        int v2 = edges[i][1];
        adj[v1].add(v2);
        adj[v2].add(v1);
    }

    Queue<Integer> queue = new LinkedList<>();

    for (int i = 0; i < n; i++) {
        if (adj[i].size() == 1)
            queue.offer(i);
    }

    while (n > 2) {
        int size = queue.size();
        n -= size;

        for (int i = 0; i < size; i++) {
            int node = queue.poll();
            List<Integer> adjNodes = adj[node];

            for (Integer adjNode : adjNodes) {
                adj[adjNode].remove(Integer.valueOf(node));

                if (adj[adjNode].size() == 1)
                    queue.offer(adjNode);
            }
        }
    }

    while (!queue.isEmpty())
        result.add(queue.poll());

    return result;
}