🌳🔄 Сортировка уровней дерева через BFS и минимизацию перестановок

leetcoder, 23-12-2024 ,

537

Очередная наша задача - 2471. Minimum Number of Operations to Sort a Binary Tree by Level

🚀 Описание задачи

Дано бинарное дерево. На каждом уровне дерева нужно отсортировать значения узлов в строго возрастающем порядке, минимизируя количество операций. За одну операцию можно поменять значения двух узлов одного уровня местами.

🧠 Идея

Для решения задачи:
1. Выполним обход дерева по уровням и соберем значения узлов для каждого уровня.
2. Для каждого уровня определим минимальное количество перестановок, необходимых для сортировки значений, используя алгоритм обнаружения циклов.

📋 Подробности подхода

Сбор уровней:
- Используем std::iter::successors для выполнения обхода дерева по уровням.
- На каждом шаге собираем значения текущего уровня и формируем следующий уровень из дочерних узлов.
Минимальные перестановки:
- Для каждого уровня создаем массив индексов, отсортированный по значениям.
- Используя алгоритм обнаружения циклов, подсчитываем минимальное количество операций для приведения массива к упорядоченному состоянию.
Подсчет результата:
- Суммируем количество перестановок для всех уровней.

⏱️ Асимптотика

Время:
- Сбор уровней: O(n), где n — количество узлов в дереве.
- Сортировка значений: O(k·log ⁡k) для уровня из k узлов.
- Обнаружение циклов: O(k) для уровня из k узлов.
- Общее время: O(n+∑k_i·log ⁡k_i), где k_i — размер каждого уровня.
Память:
- Очередь для BFS: O(w), где w — максимальная ширина дерева.
- Хранение уровней: O(n).
- Общая память: O(n).

💻 Исходный код

// 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;

impl Solution {
    /// Returns the minimum number of operations to make each level of the binary tree sorted.
    pub fn minimum_operations(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        let levels = Self::fill_levels(root);
        levels.into_iter().map(Self::count_swaps).sum()
    }

    /// Collects node values level by level using `std::iter::successors`.
    fn fill_levels(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<Vec<i32>> {
        std::iter::successors(
            root.map(|node| vec![node]), // Start with the root node.
            |current_level| {
                let mut next_level = Vec::new();
                for node in current_level {
                    let node = node.borrow();
                    // Add left and right children of the current node to the next level.
                    if let Some(left) = &node.left {
                        next_level.push(left.clone());
                    }
                    if let Some(right) = &node.right {
                        next_level.push(right.clone());
                    }
                }
                // Continue with the next level if it's not empty.
                (!next_level.is_empty()).then(|| next_level)
            },
        )
        .map(|level| {
            // Extract values from the nodes at the current level.
            level.into_iter().map(|node| node.borrow().val).collect()
        })
        .collect()
    }

    /// Calculates the minimum swaps to sort an array using cycle detection.
    fn count_swaps(vals: Vec<i32>) -> i32 {
        let mut indices: Vec<_> = (0..vals.len()).map(Some).collect();
        // Sort indices based on the values they point to.
        indices.sort_by_key(|&i| vals[i.unwrap()]);

        let mut swaps = 0;
        for i in 0..vals.len() {
            if let Some(mut j) = indices[i] {
                indices[i] = None; // Mark the index as visited.
                while let Some(next) = indices[j] {
                    indices[j] = None;
                    j = next; 
                    swaps += 1; // Increment swaps for each step in the cycle.
                }
            }
        }
        swaps
    }
}