29.02.2024
1609. Even Odd Tree medium
blog post
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/523
Problem TLDR
Binary tree levels are odd increasing and even decreasing.
Intuition
Just use level-order BFS traversal.
Approach
Let’s try to make code shorter by simplifying the if
condition.
Complexity
Time complexity:
O(n)Space complexity:
O(n), the last level of the Binary Tree is almostn/2
nodes.
Code
fun isEvenOddTree(root: TreeNode?) = ArrayDeque<TreeNode>().run {
root?.let { add(it) }
var inc = true
while (size > 0) {
var prev = 0
repeat(size) { removeFirst().run {
if (`val` % 2 > 0 != inc || `val` == prev
|| `val` < prev == inc && prev > 0) return false
left?.let { add(it) }; right?.let { add(it) }
prev = `val`
}}
inc = !inc
}; true
}
pub fn is_even_odd_tree(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
let mut q = VecDeque::new();
if let Some(n) = root { q.push_back(n) }
let mut inc = true;
while !q.is_empty() {
let mut prev = 0;
for _ in 0..q.len() { if let Some(n) = q.pop_front() {
let n = n.borrow(); let v = n.val;
if (v % 2 > 0) != inc || v == prev
|| (v < prev) == inc && prev > 0 { return false }
if let Some(l) = n.left.clone() { q.push_back(l) }
if let Some(r) = n.right.clone() { q.push_back(r) }
prev = v
}}
inc = !inc
} true
}