use std::rc::Rc;
use std::cell::RefCell;
use std::cmp::max;
impl Solution {
    pub fn btree_game_winning_move(root: Option<Rc<RefCell<TreeNode>>>, n: i32, x: i32) -> bool {
        fn count_sub_tree_nodes(node: Option<&Rc<RefCell<TreeNode>>>, x : i32,
                                left : &mut i32, right : &mut i32) -> i32 {
            if let Some(n) = node {
                let l = count_sub_tree_nodes(n.borrow().left.as_ref(), x, left, right);
                let r = count_sub_tree_nodes(n.borrow().right.as_ref(), x, left, right);
                if x == n.borrow().val {
                    *left = l; *right = r;
                }
                return l + r + 1;
            } else {
                return 0;
            }
        };

        let mut left = 0;
        let mut right = 0;
        let count = count_sub_tree_nodes(root.as_ref(), x, &mut left, &mut right);
        return max(max(left, right), n - left - right - 1) > n / 2;
    }
}

use std::rc::Rc;
use std::cell::RefCell;
use std::cmp::max;

impl Solution {
    pub fn compute_depth(node : Option<&Rc<RefCell<TreeNode>>>) -> u32 {
        if let Some(n) = node {
            return 1 + max(Solution::compute_depth(n.borrow().left.as_ref()),
                           Solution::compute_depth(n.borrow().right.as_ref()));
        } else {
            return 0;
        }
    }

    pub fn lca_deepest_leaves(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
        if let Some(node) = root.clone() {
            let (l, r) = (Solution::compute_depth(node.borrow().left.as_ref()),
                          Solution::compute_depth(node.borrow().right.as_ref()));
            if l == r {
                return Some(node);
            } else if l < r {
                return Solution::lca_deepest_leaves(node.borrow().right.clone());
            } else {
                return Solution::lca_deepest_leaves(node.borrow().left.clone());
            }
        } else {
            return None;
        }
    }
}

use std::vec::Vec;

struct MyCircularDeque {
    v: Vec<i32>,
    head : usize,
    tail : usize,
    count : usize
}

/**
 * `&self` means the method takes an immutable reference.
 * If you need a mutable reference, change it to `&mut self` instead.
 */
impl MyCircularDeque {

    /** Initialize your data structure here. Set the size of the deque to be k. */
    fn new(k: i32) -> Self {
        let mut vec = Vec::with_capacity(k.clone() as usize);
        vec.resize(k.clone() as usize, 0);
        MyCircularDeque {
            v : vec,
            head : k as usize - 1, tail : 0, count : 0
        }
    }

    /** Adds an item at the front of Deque. Return true if the operation is successful. */
    fn insert_front(&mut self, value: i32) -> bool {
        if self.is_full() {
            return false;
        }

        self.v[self.head.clone()] = value;
        self.head = (self.head + self.v.len() - 1) % self.v.len();
        self.count += 1;
        return true;
    }

    /** Adds an item at the rear of Deque. Return true if the operation is successful. */
    fn insert_last(&mut self, value: i32) -> bool {
        if self.is_full() {
            return false;
        }

        self.v[self.tail.clone()] = value;
        self.tail = (self.tail + 1) % self.v.len();
        self.count += 1;
        return true;
    }

    /** Deletes an item from the front of Deque. Return true if the operation is successful. */
    fn delete_front(&mut self) -> bool {
        if self.is_empty() {
            return false;
        }
        self.head = (self.head + 1) % self.v.len();
        self.count -= 1;
        return true;
    }

    /** Deletes an item from the rear of Deque. Return true if the operation is successful. */
    fn delete_last(&mut self) -> bool {
        if self.is_empty() {
            return false;
        }
        self.tail = (self.tail + self.v.len() - 1) % self.v.len();
        self.count -= 1;
        return true;
    }

    /** Get the front item from the deque. */
    fn get_front(&self) -> i32 {
        if self.is_empty() {
            return - 1;
        }
        return self.v[(self.head.clone() + 1) % self.v.len()];
    }

    /** Get the last item from the deque. */
    fn get_rear(&self) -> i32 {
        if self.is_empty() {
            return -1;
        }
        return self.v[(self.tail - 1 + self.v.len()) % self.v.len()];
    }

    /** Checks whether the circular deque is empty or not. */
    fn is_empty(&self) -> bool {
        return self.count == 0;
    }

    /** Checks whether the circular deque is full or not. */
    fn is_full(&self) -> bool {
        return self.count == self.v.len();
    }
}