LeetCode Entry

2415. Reverse Odd Levels of Binary Tree

20.12.2024 medium 2024 kotlin rust

Odd-levels reversal in a perfect tree

2415. Reverse Odd Levels of Binary Tree medium blog post substack youtube deep-dive 1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/838

Problem TLDR

Odd-levels reversal in a perfect tree #medium #dfs #bfs #tree

Intuition

The most straightforward way is a level-order Breadth-First Search traversal. Remember the previous layer, adjust current values accordingly.

The more interesting way is how you can do it recursively:

  • pass outer-left and outer-right values a and b (and a depth)
  • pass inner-right and inner-left values as a and b
  • swapping a and b will result in the all level reversal (that’s an interesting fact that should be observed and discovered until understood)

Approach

  • let’s implement both BFS and DFS
  • remember to reverse only odd levels
  • rewrite the values instead of the pointers, much simpler code

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(n)\) or O(log(n)) for recursion

Code


    fun reverseOddLevels(root: TreeNode?): TreeNode? {
        fun f(l: TreeNode?, r: TreeNode?, d: Int) {
            l ?: return; r ?: return
            if (d % 2 > 0) l.`val` = r.`val`.also { r.`val` = l.`val` }
            f(l.left, r.right, d + 1)
            f(l.right, r.left, d + 1)
        }
        f(root?.left, root?.right, 1)
        return root
    }



    pub fn reverse_odd_levels(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
        let Some(r) = root.clone() else { return root };  let mut q = VecDeque::from([r]);
        let (mut i, mut vs) = (0, vec![]);
        while q.len() > 0 {
            let mut l = vec![];
            for _ in 0..q.len() {
                let n = q.pop_front().unwrap(); let mut n = n.borrow_mut();
                if i % 2 > 0 && vs.len() > 0 { n.val = vs.pop().unwrap(); }
                if let Some(x) = n.left.clone() { l.push(x.borrow().val); q.push_back(x); }
                if let Some(x) = n.right.clone() { l.push(x.borrow().val); q.push_back(x); }
            }
            vs = l; i += 1
        }
        root
    }



    TreeNode* reverseOddLevels(TreeNode* root) {
        auto f = [](this auto const& f, TreeNode* l, TreeNode* r, int d) {
            if (!l || !r) return; if (d % 2) swap(l->val, r->val);
            f(l->left, r->right, d + 1); f(l->right, r->left, d + 1);
        };
        f(root->left, root->right, 1); return root;
    }