// Definition for a binary tree node.
#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
  pub val: i32,
  pub left: Option<Rc<RefCell<TreeNode>>>,
  pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
  #[inline]
  pub fn new(val: i32) -> Self {
    TreeNode {
      val,
      left: None,
      right: None
    }
  }
}
use std::rc::Rc;
use std::cell::RefCell;

struct Solution {}

impl Solution {
    pub fn is_even_odd_tree(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
      let root = root.unwrap();
      let mut stack = vec![root];
      let mut layer = vec![];
      let mut odd = false;
      let mut now = 0;
      while stack.len() != 0 {
        while stack.len() != 0 {
          let node = stack.remove(0);
          let n = node.borrow();
          // println!("{}", n.val);
          if (now != 0 && (((now - n.val) > 0) ^ odd)) || ((n.val % 2 == 0) ^ odd) || now == n.val  {
            // println!("{} {} {}", now, n.val, odd);
            return false;
          }
          now = n.val; 
          if let Some(l) = &n.left {
            layer.push(l.clone());
          }
          if let Some(r) = &n.right {
            layer.push(r.clone());
          }
        }
        stack = layer;
        layer = vec![];
        odd = !odd;
        now = 0;
      } 
      true
    }
}