use std::collections::HashSet;
use std::iter::FromIterator;
impl Solution {
    pub fn remove_vowels(s: String) -> String {
        let (mut ans, mut j) = ("".to_string(), 0);
        let vowel_set : HashSet<char> = HashSet::from_iter(vec!['a', 'e', 'i', 'o', 'u']);
        while j < s.len() {
            let sj = s.chars().nth(j).unwrap();
            if !vowel_set.contains(&sj) {
                ans.push(sj);
            }
            j+= 1;
        }
        return ans;
    }
}

use std::rc::Rc;
use std::cell::RefCell;
use std::borrow::Borrow;

impl Solution {
    fn dfs(root: Option<&Rc<RefCell<TreeNode>>>, ans: &mut f64) -> (i32, i32) {
        if let Some(node) = root {
            let (l, r) = (Self::dfs(RefCell::borrow(&node).left.as_ref(), ans),
                          Self::dfs(RefCell::borrow(&node).right.as_ref(), ans));
            let sum = l.0 + r.0 + RefCell::borrow(&node).val;
            let total = 1 + l.1 + r.1;
            let avg = sum as f64 / total as f64;
            if avg > *ans {
                *ans = avg;
            }
            return (sum, total);
        } else {
            return (0, 0);
        }
    }

    pub fn maximum_average_subtree(root: Option<Rc<RefCell<TreeNode>>>) -> f64 {
        let mut ans = 0.;
        if root.is_none() {
            return ans;
        }
        Self::dfs(Some(&root.unwrap()), &mut ans);
        return ans;
    }
}

impl Solution {
    pub fn mct_from_leaf_values(arr: Vec<i32>) -> i32 {
        let (mut ans, n) = (0, arr.len());
        let mut stack = vec![];
        stack.push(std::i32::MAX);
        for a in &arr {
            while stack.last().unwrap() <= a {
                let mid = stack.last().unwrap().clone();
                stack.pop();
                ans += mid * std::cmp::min(stack.last().unwrap(), a);
            }
            stack.push(*a);
        }

        let mut i = 2;
        while i < stack.len() {
            ans += stack[i] * stack[i - 1];
            i += 1;
        }
        return ans;
    }
}