# [LeetCode] 310. Minimum Height Trees 最小高度树

2021年09月15日 阅读数：1

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.html

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).java

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`.node

Example 1 :python

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

0
|
1
/ \
2   3

Output: ``
```

Example 2 :app

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

0  1  2
\ | /
3
|
4
|
5

Output: `[3, 4]````

Note:less

• 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.

Java:post

```public List<Integer> findMinHeightTrees(int n, int[][] edges) {
List<Integer> result = new ArrayList<Integer>();
if(n==0){
return result;
}
if(n==1){
return result;
}

ArrayList<HashSet<Integer>> graph = new ArrayList<HashSet<Integer>>();
for(int i=0; i<n; i++){
}

for(int[] edge: edges){
}

for(int i=0; i<n; i++){
if(graph.get(i).size()==1){
leaves.offer(i);
}
}

if(leaves.size()==0){
return result;
}

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

for(int l: leaves){
int neighbor = graph.get(l).iterator().next();
graph.get(neighbor).remove(l);
if(graph.get(neighbor).size()==1){
}
}

leaves = newLeaves;
}

return leaves;
}　　```

Python:url

```class Solution(object):
def findMinHeightTrees(self, n, edges):
"""
:type n: int
:type edges: List[List[int]]
:rtype: List[int]
"""
if n == 1:
return 

neighbors = collections.defaultdict(set)
for u, v in edges:

pre_level, unvisited = [], set()
for i in xrange(n):
if len(neighbors[i]) == 1:  # A leaf.
pre_level.append(i)

# A graph can have 2 MHTs at most.
# BFS from the leaves until the number
# of the unvisited nodes is less than 3.
while len(unvisited) > 2:
cur_level = []
for u in pre_level:
unvisited.remove(u)
for v in neighbors[u]:
if v in unvisited:
neighbors[v].remove(u)
if len(neighbors[v]) == 1:
cur_level.append(v)
pre_level = cur_level

return list(unvisited)```

C++:code

```// Time:  O(n)
// Space: O(n)

class Solution {
public:
vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
if (n == 1) {
return {0};
}

unordered_map<int, unordered_set<int>> neighbors;
for (const auto& e : edges) {
int u, v;
tie(u, v) = e;
neighbors[u].emplace(v);
neighbors[v].emplace(u);
}

vector<int> pre_level, cur_level;
unordered_set<int> unvisited;
for (int i = 0; i < n; ++i) {
if (neighbors[i].size() == 1) {  // A leaf.
pre_level.emplace_back(i);
}
unvisited.emplace(i);
}

// A graph can have 2 MHTs at most.
// BFS from the leaves until the number
// of the unvisited nodes is less than 3.
while (unvisited.size() > 2) {
cur_level.clear();
for (const auto& u : pre_level) {
unvisited.erase(u);
for (const auto& v : neighbors[u]) {
if (unvisited.count(v)) {
neighbors[v].erase(u);
if (neighbors[v].size() == 1) {
cur_level.emplace_back(v);
}
}
}
}
swap(pre_level, cur_level);
}

vector<int> res(unvisited.begin(), unvisited.end());
return res;
}
};
```

Course Schedule II

Course Schedule

Clone Graph