На нашей новой задаче 2415. Reverse Odd Levels of Binary Tree есть повод продемонстировать продвинутые методы Rust работы с итераторами (std::iter::successors & std::iter::zip), а также "непристойную" работу c реф-каунт ячейками :(
📜 Описание задачи
Дано идеальное бинарное дерево. Требуется изменить порядок значений узлов на всех нечетных уровнях дерева.
Идеальное дерево — это дерево, где у каждого узла два потомка, а все листья находятся на одном уровне.
💡 Идея
Мы адаптируем BFS для обхода дерева по уровням. На каждом уровне проверяется, нужно ли инвертировать порядок значений (для нечетных уровней). С помощью вспомогательной функции формируются следующие уровни дерева.
📋 Подробности подхода
-
Вспомогательная функция
next_level:
- Формирует следующий уровень дерева, собирая всех левых и правых потомков текущих узлов.
-
Завершение обработки:
- Проверка, что текущий уровень является листовым, выполняется через условие
nodes[0].borrow().left.is_none().
- При достижении уровня листьев обработка завершается.
-
Обход уровней с помощью
std::iter::successors:
- Используется функциональный подход для последовательного формирования уровней дерева. Итератор автоматически останавливается при достижении листового уровня.
-
Инверсия значений:
- На нечетных уровнях значения узлов меняются местами с помощью двух индексов (
left и right), начиная с концов уровня и двигаясь к центру.
📊 Асимптотики
-
Временная сложность:
O(N)
Каждый узел посещается ровно один раз, а инверсия на нечетных уровнях требует O(W), где W — ширина уровня.
-
Пространственная сложность:
O(W)
Память используется для хранения текущего уровня дерева, что пропорционально максимальной ширине дерева (числу узлов на самом широком уровне).
💻 Исходный код
// 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>>>,
// }
use std::rc::Rc;
use std::cell::RefCell;
use std::iter::{successors, zip};
type LevelNodes = Vec<Rc<RefCell<TreeNode>>>;
impl Solution {
// Generate the next level of nodes and increment the level index
fn next_level((nodes, level): &(LevelNodes, usize)) -> Option<(LevelNodes, usize)> {
// If the first node has no left child, we have reached the leaf level
if nodes[0].borrow().left.is_none() {
return None;
}
// Collect all left and right children of the current level nodes
let next_nodes: LevelNodes = nodes.iter()
.flat_map(|node| {
let node = node.borrow();
vec![node.left.clone().unwrap(), node.right.clone().unwrap()]
}).collect();
Some((next_nodes, level + 1))
}
pub fn reverse_odd_levels(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
// Early return if the tree is empty
if root.is_none() {
return root;
}
// Create an iterator for all levels of the tree
let levels_iter = successors(
Some((vec![root.clone().unwrap()], 0)),
Self::next_level
);
// Iterate over levels and reverse node values at odd levels
for (level_nodes, level_index) in levels_iter {
if level_index % 2 == 1 {
let indices = 0..level_nodes.len();
for (left, right) in zip(indices.clone(), indices.rev()) {
if left < right {
// Swap values of nodes from both ends of the level
let val_left = level_nodes[left].borrow().val;
let val_right = level_nodes[right].borrow().val;
level_nodes[left].borrow_mut().val = val_right;
level_nodes[right].borrow_mut().val = val_left;
} else {
break
}
}
}
}
root
}
}