Reverse odd levels of binary tree

Tree Depth-First Search Breadth-First Search Binary Tree

86.7% acceptance

Feb 27, 2026

1760

Given the root of a perfect binary tree, reverse the node values at each odd level of the tree. For example, suppose the node values at level 3 are [2,1,3,4,7,11,29,18], then it should become [18,29,11,7,4,3,1,2]. Return the root of the reversed tree. A binary tree is perfect if all parent nodes have two children and all leaves are on the same level. The level of a node is the number of edges along the path between it and the root node.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
  pub fn reverse_odd_levels(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
    if root.is_none() {
      return root;
    }
    let mut level = vec![root.clone().unwrap()];
    let mut is_odd = false;
    loop {
      if is_odd {
        let n = level.len();
        let mut lo = 0;
        let mut hi = n - 1;
        while lo < hi {
          let lv = level[lo].borrow().val;
          let rv = level[hi].borrow().val;
          level[lo].borrow_mut().val = rv;
          level[hi].borrow_mut().val = lv;
          lo += 1;
          hi -= 1;
        }
      }
      let mut next = vec![];
      for node in &level {
        if let Some(l) = node.borrow().left.clone() {
          next.push(l);
        }
        if let Some(r) = node.borrow().right.clone() {
          next.push(r);
        }
      }
      if next.is_empty() {
        break;
      }
      level = next;
      is_odd = !is_odd;
    }
    root
  }
}