use std::collections::VecDeque;

impl Solution {
    pub fn deck_revealed_increasing(deck: Vec<i32>) -> Vec<i32> {
        let mut d = deck;
        d.sort();
        let (mut q, n, mut ans) = (VecDeque::new(), d.len(), vec![0; d.len()]);
        for i in 0..n {
            q.push_back(i);
        }
        for i in 0..n {
            let mut cur = q.front().unwrap().clone();
            ans[cur] = d[i];
            q.pop_front();
            if q.is_empty() {
                break;
            }
            
            cur = q.front().unwrap().clone();            
            q.push_back(cur);
            q.pop_front();
        }
        return ans;
    }
}

use std::collections::HashMap;

impl Solution {
    fn compare(w1: &String, w2: &String, map: &HashMap<char, usize>) -> bool {
        let size = std::cmp::min(w1.len(), w2.len());
        for i in 0..size {
            let (i1, i2) = (
                *map.get(&w1.chars().nth(i).unwrap()).unwrap(),
                *map.get(&w2.chars().nth(i).unwrap()).unwrap());
            if i1 > i2 {
                return false;
            } else if i1 == i2 {
                continue;
            } else {
                return true;
            }
        }

        if w1.len() > w2.len() {
            return false;
        }

        return true;
    }
    pub fn is_alien_sorted(words: Vec<String>, order: String) -> bool {
        let mut map = HashMap::new();
        for i in 0..order.len() {
            map.insert(order.chars().nth(i).unwrap(), i);
        }
        for i in 0..words.len() - 1 {
            if Self::compare(&words[i], &words[i + 1], &map) {
                continue;
            }
            return false;
        }
        return true;
    }
}

use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    fn dfs(root: Option<&Rc<RefCell<TreeNode>>>, val: i32) -> bool {
        if let Some(n) = root {
            if RefCell::borrow(&n).val != val {
                return false;
            }
            return Self::dfs(RefCell::borrow(&n).left.as_ref(), val) &&
                   Self::dfs(RefCell::borrow(&n).right.as_ref(), val);
        } else {
            return true;
        }
    }
    pub fn is_unival_tree(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
        if let Some(n) = root {
            return Self::dfs(Some(&n), RefCell::borrow(&n).val);
        } else {
            return true;
        }
    }
}