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

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

Difficulté : moyenne

Sujets :Arbre,Recherche en largeur d'abord,Arbre binaire

On vous donne leracined'un arbre binaire à valeurs uniques.

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

Renvoie 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 qui le relie au nœud racine.

Exemple 1 :

• 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 3.
  • On peut prouver que 3 est le nombre minimum d’opérations nécessaires.

Exemple 2 :

• 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 3.
  • On peut prouver que 3 est le nombre minimum d’opérations nécessaires.

Exemple 3 :

• Entrée : racine = [1,2,3,4,5,6]
• Sortie : 0
• Explication : Chaque niveau est déjà trié par ordre croissant donc renvo...
  [Courte citation de 8% de l'article original]