leetcode_solutions/
n310_minimum_height_trees.rs

1/*
2 * No: 310
3 * Title: Minimum Height Trees
4 */
5
6use crate::Solution;
7
8impl Solution {
9    pub fn find_min_height_trees(n: i32, edges: Vec<Vec<i32>>) -> Vec<i32> {
10        use std::collections::HashSet;
11        let mut n = n as usize;
12        let mut adjacent_nodes: Vec<HashSet<usize>> = vec![HashSet::new(); n];
13
14        if n == 1 {
15            return vec![0];
16        }
17
18        for edge in edges.iter() {
19            adjacent_nodes[edge[0] as usize].insert(edge[1] as usize);
20            adjacent_nodes[edge[1] as usize].insert(edge[0] as usize);
21        }
22
23        let mut leaves = vec![];
24
25        for node in 0..(n) {
26            if adjacent_nodes[node].len() == 1 {
27                leaves.push(node);
28            }
29        }
30
31        while n > 2 {
32            n -= leaves.len();
33            let mut new_leaves = vec![];
34            for i in 0..leaves.len() {
35                let leaf = leaves[i];
36                let parent = (*adjacent_nodes[leaf].iter().next().unwrap()).clone();
37                adjacent_nodes[parent].remove(&leaf);
38                if adjacent_nodes[parent].len() == 1 {
39                    new_leaves.push(parent);
40                }
41            }
42            leaves = new_leaves;
43        }
44
45        leaves.into_iter().map(|leaf| leaf as i32).collect()
46    }
47}
leetcode_solutions/n310_minimum_height_trees.rs

leetcode_solutions/
n310_minimum_height_trees.rs
