Binary tree zigzag level order traversal

Tree Breadth-First Search Binary Tree

63.2% acceptance

Feb 27, 2026

11978

358

Given the root of a binary tree, return the zigzag level order traversal of its nodes' values. (i.e., from left to right, then right to left for the next level and alternate between).

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 zigzag_level_order(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());
    let mut left_to_right = true;
    
    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);
          }
        }
      }
      
      if !left_to_right {
        level.reverse();
      }
      result.push(level);
      left_to_right = !left_to_right;
    }
    
    result
  }
}