310. Minimum Height Trees

310. Minimum Height Trees

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.

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 1:

Given n = 4, edges = [[1, 0], [1, 2], [1, 3]]

0 | 1 / \ 2 3

return [1]

Example 2:

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

0 1 2 \ | / 3 | 4 | 5

return [3, 4]

Note:

(1) 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.”

(2) The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.

思路： 先计算degree为1的节点，这些节点只和一个节点相连，所以这些是leaf节点。逐个去除掉leaf节点以后我们可以尝试计算上一层leaf，继续and继续，直到最后我们剩下一个节点或者两个节点，就是我们要求的root nodes。 Time Complexity - O(n)， Space Complexity - O(n)

class Solution { public List findMinHeightTrees(int n, int[][] edges) { List leaves = new ArrayList<>(); if (n == 1) return Collections.singletonList(0); List> graph = new ArrayList<>(); for (int i = 0; i < n; i++) graph.add(new HashSet<>()); for (int[] edge : edges) { graph.get(edge[0]).add(edge[1]); graph.get(edge[1]).add(edge[0]); } for (int i = 0; i < n; i++) { if (graph.get(i).size() == 1) leaves.add(i); } while (n > 2) { n -= leaves.size(); List newLeaves = new ArrayList<>(); for (int leaf : leaves) { for (int j : graph.get(leaf)) { graph.get(j).remove(leaf); if (graph.get(j).size() == 1) newLeaves.add(j); } } leaves = newLeaves; } return

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。