. Trouver la plus grande valeur dans chaque rangée d'arbre

515. Trouvez la plus grande valeur dans chaque rangée d'arbres

Difficulté :Moyen

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

Étant donné la racine d'un arbre binaire, renvoie un tableau de la plus grande valeur dans chaque ligne de l'arbre (indexé à 0).

Exemple 1 :

• Entrée : racine = [1,3,2,5,3,null,9]
• Sortie : [1,3,9]

Exemple 2 :

• Entrée : racine = [1,2,3]
• Sortie : [1,3]

Contraintes :

• Le nombre de nœuds dans l'arborescence sera compris entre [0, 10⁴].
• -2³¹ <= Node.val <= 2³¹ - 1

Solution :

Le problème "Trouver la plus grande valeur dans chaque ligne d'arbre" nécessite d'identifier la plus grande valeur présente à chaque niveau (ligne) d'un arbre binaire. Étant donné un arbre binaire, le but est de parcourir l’arbre ligne par ligne et de collecter la valeur maximale de chaque ligne. Ce problème implique des techniques fondamentales de traversée d'arbres telles que la Breadth-First Search (BFS) ou la Depth-First Search (DFS).

Points clés

1. Tree Traversal : La solution consiste à parcourir tous les niveaux de l'arbre binaire pour identifier la plus grande valeur à chaque niveau.
2. Breadth-First Search (BFS) : BFS convient au parcours niveau par niveau, ce qui simplifie la recherche de la plus grande valeur dans chaque ligne.
3. Contraintes : gérez les cas extrêmes comme un arbre vide et des nœuds avec des valeurs entières grandes ou petites dans la plage de contraintes.

Approche

L'approche la plus simple pour trouver la plus grande valeur dans chaque ligne consiste à utiliser BFS :

• Parcourez l'arbre niveau par niveau.
• Pour chaque niveau, gardez une trace de la plus grande valeur.

Alternativement, DFS peut également être utilisé :

• Parcourez l'arbre de manière récursive et conservez un enregistrement de la valeur maximale à chaque profondeur.

Planifier

1. Initialisez un tableau pour stocker les plus grandes valeurs de chaque ligne.
2. Utilisez une file d'attente pour le parcours BFS :
   • Commencez par le nœud racine.
   • Traitez tous les nœuds du niveau actuel avant de passer au suivant.
3. Pour chaque niveau :
   • Parcourez tous les nœuds et trouvez la valeur maximale.
   • Ajoutez cette valeur au tableau de résultats.
4. Renvoyer le tableau de résultats après avoir terminé le parcours.

Étapes de la solution

1. Vérifier l'entrée : Si la racine est nulle, renvoie un tableau vide.
2. Configurer BFS :
   • Utilisez une file d'attente initialisée avec le nœud racine.
   • Initialisez un tableau de résultats vide.
3. Niveaux de traversée :
   • Pour chaque niveau, suivez la valeur maximale.
   • Ajoutez des nœuds enfants à la file d'attente pour le niveau suivant.
4. Mise à jour des résultats :
   • Ajoutez la valeur maximale de chaque niveau au tableau de résultats.
5. Retour des résultats : renvoie le tableau de résultats contenant les plus grandes valeurs pour chaque ligne.

Implémentons cette solution en PHP : 515. Trouvez la plus grande valeur dans chaque rangée d'arbres

val = $val;
        $this->left = $left;
        $this->right = $right;
    }
}

/**
 * @param TreeNode $root
 * @return Integer[]
 */
function largestValues($root) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$root = new TreeNode(1);
$root->left = new TreeNode(3);
$root->right = new TreeNode(2);
$root->left->left = new TreeNode(5);
$root->left->right = new TreeNode(3);
$root->right->right = new TreeNode(9);

print_r(largestValues($root)); // Output: [1, 3, 9]
?>





  
  
  Explication:



  
  
  Entrée : [1,3,2,5,3,null,9]




Niveau 0 : Valeurs des nœuds : [1] → Maximum : 1.

Niveau 1 : Valeurs des nœuds : [3, 2] → Maximum : 3.

Niveau 2 : Valeurs des nœuds : [5, 3, 9] → Maximum : 9.
#### Sortie : [1, 3, 9].



  
  
  Complexité temporelle




BFS Traversal : Chaque nœud est traité une fois → O(n).

Trouver le maximum : effectué pendant le parcours → O(1) par niveau.

Total : O(n).



  
  
  Complexité spatiale




Queue Storage : Au plus, la largeur de l'arbre (nombre de nœuds au plus grand niveau) → O(w) où w est la largeur maximale de l'arbre.



  
  
  Sortie pour exemple


Entrée : root = [1,3,2,5,3,null,9]


Sortie : [1, 3, 9].

Cette solution basée sur BFS calcule efficacement la plus grande valeur de chaque ligne d'arbre avec une complexité temporelle linéaire. Il gère efficacement les grands arbres, les valeurs négatives et les cas limites comme les arbres vides.

Liens de contact

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 :

LinkedIn
GitHub



          

            
  

            
        
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!