Nombre minimum d'opérations pour trier un arbre binaire par niveau-tutoriel php-php.cn

Nombre minimum d'opérations pour trier un arbre binaire par niveau

Mary-Kate Olsen

Libérer： 2025-01-03 02:42:37

original

651 Les gens l'ont consulté

2471. Nombre minimum d'opérations pour trier un arbre binaire par niveau

Difficulté :Moyen

Sujets : Arbre, recherche en largeur d'abord, arbre binaire

Vous recevez la racine d'un arbre binaire avec valeurs uniques.

En une seule opération, vous pouvez choisir deux nœuds au même niveau et échanger leurs valeurs.

Renvoyer le nombre minimum d'opérations nécessaires pour trier les valeurs de chaque niveau dans un ordre strictement croissant.

Le niveau d'un nœud est le nombre d'arêtes le long du chemin entre celui-ci et le nœud racine.

Exemple 1 :

Minimum Number of Operations to Sort a Binary Tree by Level

Entrée : racine = [1,4,3,7,6,8,5,null,null,null,null,9,null,10]
Sortie : 3
Explication :
- Échangez 4 et 3. Le 2ème niveau devient [3,4].
- Échangez 7 et 5. Le 3ème niveau devient [5,6,8,7].
- Échangez 8 et 7. Le 3ème niveau devient [5,6,7,8].
- Nous avons utilisé 3 opérations donc renvoyez-en 3.
- Il peut être prouvé que 3 est le nombre minimum d'opérations nécessaires.

Exemple 2 :

Minimum Number of Operations to Sort a Binary Tree by Level

Entrée : racine = [1,3,2,7,6,5,4]
Sortie : 3
Explication :
- Échangez 3 et 2. Le 2ème niveau devient [2,3].
- Échangez 7 et 4. Le 3ème niveau devient [4,6,5,7].
- Échangez 6 et 5. Le 3ème niveau devient [4,5,6,7].
- Nous avons utilisé 3 opérations donc renvoyez-en 3.
- Il peut être prouvé que 3 est le nombre minimum d'opérations nécessaires.

Exemple 3 :

Minimum Number of Operations to Sort a Binary Tree by Level

Entrée : racine = [1,2,3,4,5,6]
Sortie : 0
Explication : Chaque niveau est déjà trié par ordre croissant donc retournez 0.

Contraintes :

Le nombre de nœuds dans l'arborescence est compris entre [1, 10⁵].
1 <= Node.val <= 10⁵
Toutes les valeurs de l'arbre sont uniques.

Indice :

Nous pouvons regrouper les valeurs niveau par niveau et résoudre chaque groupe indépendamment.
Faites BFS pour regrouper la valeur niveau par niveau.
Trouvez le nombre minimum d'échanges pour trier le tableau de chaque niveau.
Lors de l'itération sur le tableau, vérifiez l'élément actuel, et s'il n'est pas dans le bon index, remplacez cet élément par l'index de l'élément qui aurait dû arriver.

Solution :

Le problème consiste à trier les valeurs d'un arbre binaire niveau par niveau dans un ordre strictement croissant avec le nombre minimum d'opérations. Dans chaque opération, nous pouvons échanger les valeurs de deux nœuds qui sont au même niveau. L'objectif est de déterminer le nombre minimum de ces opérations nécessaires pour atteindre l'ordre trié.

Points clés :

Niveaux de l'arbre binaire : Chaque niveau de l'arbre binaire doit avoir des valeurs triées par ordre strictement croissant.
Valeurs uniques : tous les nœuds ont des valeurs uniques, ce qui facilite le tri car il n'y a pas de doublons.
BFS pour le regroupement de niveaux : utilisez la recherche en largeur d'abord (BFS) pour parcourir l'arborescence et regrouper les nœuds par leurs niveaux.
Swaps minimum : Pour chaque niveau, nous devons trouver le nombre minimum d'échanges requis pour trier les valeurs des nœuds à ce niveau.
Contraintes : L'arbre peut avoir jusqu'à 10^5 nœuds, la solution doit donc être efficace.

Approche:

BFS Traversal : effectuez un BFS pour parcourir l'arborescence et collecter les valeurs des nœuds à chaque niveau.
Tri de chaque niveau : Pour chaque niveau, calculez le nombre minimum d'échanges pour trier les valeurs dans un ordre strictement croissant.
Décomposition en cycle : L'observation clé pour minimiser les échanges est que le tri d'un tableau peut être considéré comme un échange d'éléments dans des cycles. Le nombre minimum d'échanges pour chaque cycle d'éléments égarés est la durée du cycle moins un.
Accumulation d'échanges : additionnez les échanges pour chaque niveau pour obtenir le nombre total d'échanges requis.

Plan:

BFS : parcourez l'arborescence à l'aide de BFS pour collecter des nœuds à chaque niveau.
Tri de chaque niveau : Triez les valeurs à chaque niveau et calculez le nombre minimum d'échanges.
Calculer les échanges : utilisez la décomposition par cycle pour trouver les échanges minimaux nécessaires pour trier les nœuds à chaque niveau.

Implémentons cette solution en PHP : 2471. Nombre minimum d'opérations pour trier un arbre binaire par niveau

<?php
/**
 * @param TreeNode $root
 * @return Integer
 */
function minimumOperations($root) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * Function to calculate minimum swaps to sort an array
 *
 * @param $arr
 * @return int
 */
function minSwapsToSort($arr) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}
?>




<h3>
  
  
  Explication:
</h3>

<ol>
<li>
<p><strong>Étape 1 : Effectuer BFS pour regrouper les nœuds par niveau</strong> :</p>
<ul>
<li>Partez de la racine et parcourez l'arbre niveau par niveau.</li>
<li>Pour chaque nœud, ajoutez sa valeur au niveau correspondant dans le tableau des niveaux.</li>
</ul>
</li>
<li>
<p><strong>Étape 2 : Pour chaque niveau, calculez les swaps minimum pour trier les valeurs</strong> :</p>

<ul>
<li>Trier les valeurs à chaque niveau.</li>
<li>Utilisez une approche basée sur le cycle pour calculer les échanges minimaux requis pour transformer le niveau actuel en un niveau trié.</li>
</ul>
</li>
<li>
<p><strong>Décomposition du cycle</strong> :</p>

<ul>
<li>Pour chaque élément non trié, tracez son cycle (c'est-à-dire où il doit aller) et marquez les éléments comme visités.</li>
<li>Pour chaque cycle, le nombre d'échanges requis est la durée du cycle moins un.</li>
</ul>
</li>
<li>
<p><strong>Renvoyer le nombre total d'échanges</strong> :</p>

<ul>
<li>Sommez les échanges nécessaires pour chaque niveau et renvoyez le total.</li>
</ul>
</li>
</ol>

<h3>
  
  
  Exemple de procédure pas à pas :
</h3>

<h4>
  
  
  Exemple 1 :
</h4>

<p>Arbre de saisie :<br>
</p>

<div class="code" style="position:relative; padding:0px; margin:0px;"><pre class="brush:php;toolbar:false"><?php
/**
 * @param TreeNode $root
 * @return Integer
 */
function minimumOperations($root) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * Function to calculate minimum swaps to sort an array
 *
 * @param $arr
 * @return int
 */
function minSwapsToSort($arr) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}
?>

Copier après la connexion

Exemple 2 :

Complexité temporelle :

Ainsi, la complexité temporelle globale est O(N log N), ce qui est suffisamment efficace compte tenu des contraintes.

Sortie par exemple :

<?php /** * @param TreeNode $root * @return Integer */ function minimumOperations($root) { ... ... ... /** * go to ./solution.php */ } /** * Function to calculate minimum swaps to sort an array * * @param $arr * @return int */ function minSwapsToSort($arr) { ... ... ... /** * go to ./solution.php */ } ?>

Cette solution calcule efficacement le nombre minimum de swaps nécessaires pour trier chaque niveau de l'arbre binaire en utilisant BFS pour regrouper les nœuds par niveau et par décomposition en cycle afin de minimiser le nombre de swaps. La complexité temporelle de O(N log N) est optimale pour gérer des arbres avec jusqu'à 10^5 nœuds.

Si vous avez trouvé cette série utile, pensez à donner une étoile au référentiel sur GitHub ou à partager la publication sur vos réseaux sociaux préférés ?. Votre soutien signifierait beaucoup pour moi !

Si vous souhaitez du contenu plus utile comme celui-ci, n'hésitez pas à me suivre :

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!