|
8 | 8 | import java.util.Set; |
9 | 9 |
|
10 | 10 | /** |
11 | | - * 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. |
| 11 | + * 310. Minimum Height Trees |
| 12 | + * |
| 13 | + * For a undirected graph with tree characteristics, we can choose any node as the root. |
| 14 | + * The result graph is then a rooted tree. Among all possible rooted trees, those with minimum height are called minimum height trees (MHTs). |
| 15 | + * Given such a graph, write a function to find all the MHTs and return a list of their root labels. |
12 | 16 |
|
13 | 17 | Format |
14 | 18 | 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). |
|
19 | 23 |
|
20 | 24 | Given n = 4, edges = [[1, 0], [1, 2], [1, 3]] |
21 | 25 |
|
22 | | - 0 |
| 26 | + 0 |
23 | 27 | | |
24 | 28 | 1 |
25 | 29 | / \ |
|
50 | 54 | */ |
51 | 55 | public class _310 { |
52 | 56 |
|
53 | | - public List<Integer> findMinHeightTrees(int n, int[][] edges) { |
54 | | - if (n == 1) { |
55 | | - return Collections.singletonList(0); |
56 | | - } |
| 57 | + public static class Solution1 { |
| 58 | + public List<Integer> findMinHeightTrees(int n, int[][] edges) { |
| 59 | + if (n == 1) { |
| 60 | + return Collections.singletonList(0); |
| 61 | + } |
57 | 62 |
|
58 | | - List<Set<Integer>> adj = new ArrayList<>(n); |
59 | | - for (int i = 0; i < n; ++i) { |
60 | | - adj.add(new HashSet<>()); |
61 | | - } |
62 | | - for (int[] edge : edges) { |
63 | | - adj.get(edge[0]).add(edge[1]); |
64 | | - adj.get(edge[1]).add(edge[0]); |
65 | | - } |
| 63 | + List<Set<Integer>> adj = new ArrayList<>(n); |
| 64 | + for (int i = 0; i < n; ++i) { |
| 65 | + adj.add(new HashSet<>()); |
| 66 | + } |
| 67 | + for (int[] edge : edges) { |
| 68 | + adj.get(edge[0]).add(edge[1]); |
| 69 | + adj.get(edge[1]).add(edge[0]); |
| 70 | + } |
66 | 71 |
|
67 | | - List<Integer> leaves = new ArrayList<>(); |
68 | | - for (int i = 0; i < n; ++i) { |
69 | | - if (adj.get(i).size() == 1) { |
70 | | - leaves.add(i); |
| 72 | + List<Integer> leaves = new ArrayList<>(); |
| 73 | + for (int i = 0; i < n; ++i) { |
| 74 | + if (adj.get(i).size() == 1) { |
| 75 | + leaves.add(i); |
| 76 | + } |
71 | 77 | } |
72 | | - } |
73 | 78 |
|
74 | | - while (n > 2) { |
75 | | - n -= leaves.size(); |
76 | | - List<Integer> newLeaves = new ArrayList<>(); |
77 | | - for (int i : leaves) { |
78 | | - int j = adj.get(i).iterator().next(); |
79 | | - adj.get(j).remove(i); |
80 | | - if (adj.get(j).size() == 1) { |
81 | | - newLeaves.add(j); |
| 79 | + while (n > 2) { |
| 80 | + n -= leaves.size(); |
| 81 | + List<Integer> newLeaves = new ArrayList<>(); |
| 82 | + for (int i : leaves) { |
| 83 | + int j = adj.get(i).iterator().next(); |
| 84 | + adj.get(j).remove(i); |
| 85 | + if (adj.get(j).size() == 1) { |
| 86 | + newLeaves.add(j); |
| 87 | + } |
82 | 88 | } |
| 89 | + leaves = newLeaves; |
83 | 90 | } |
84 | | - leaves = newLeaves; |
| 91 | + return leaves; |
85 | 92 | } |
86 | | - return leaves; |
87 | 93 | } |
88 | | - |
89 | 94 | } |
0 commit comments