Binary tree level order traversal ii

Tree Breadth-First Search Binary Tree

67.7% acceptance

Feb 27, 2026

5154

334

Given the root of a binary tree, return the bottom-up level order traversal of its nodes' values. (i.e., from left to right, level by level from leaf to root).

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

// 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;
impl Solution {
  pub fn level_order_bottom(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<Vec<i32>> {
    use std::collections::VecDeque;
    let mut result = Vec::new();
    if root.is_none() {
      return result;
    }
    
    let mut queue = VecDeque::new();
    queue.push_back(root.unwrap());
    
    while !queue.is_empty() {
      let level_size = queue.len();
      let mut level = Vec::new();
      
      for _ in 0..level_size {
        if let Some(node) = queue.pop_front() {
          let node_borrow = node.borrow();
          level.push(node_borrow.val);
          
          if let Some(left) = node_borrow.left.clone() {
            queue.push_back(left);
          }
          if let Some(right) = node_borrow.right.clone() {
            queue.push_back(right);
          }
        }
      }
      result.push(level);
    }
    
    result.reverse();
    result
  }
}