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
use crate::Solution;
impl Solution {
pub fn find_min_height_trees(n: i32, edges: Vec<Vec<i32>>) -> Vec<i32> {
use std::collections::HashSet;
let mut n = n as usize;
let mut adjacent_nodes: Vec<HashSet<usize>> = vec![HashSet::new(); n];
if n == 1 {
return vec![0];
}
for edge in edges.iter() {
adjacent_nodes[edge[0] as usize].insert(edge[1] as usize);
adjacent_nodes[edge[1] as usize].insert(edge[0] as usize);
}
let mut leaves = vec![];
for node in 0..(n) {
if adjacent_nodes[node].len() == 1 {
leaves.push(node);
}
}
while n > 2 {
n -= leaves.len();
let mut new_leaves = vec![];
for i in 0..leaves.len() {
let leaf = leaves[i];
let parent = (*adjacent_nodes[leaf].iter().next().unwrap()).clone();
adjacent_nodes[parent].remove(&leaf);
if adjacent_nodes[parent].len() == 1 {
new_leaves.push(parent);
}
}
leaves = new_leaves;
}
leaves.into_iter().map(|leaf| leaf as i32).collect()
}
}
