Kième plus grande somme dans un arbre binaire

2583. Kième plus grande somme dans un arbre binaire

Difficulté :Moyen

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

On vous donne la racine d'un arbre binaire et un entier positif k.

La somme de niveau dans l'arbre est la somme des valeurs des nœuds qui sont au même niveau.

Renvoyer le k^ième le plus grandsomme de niveau dans l'arbre (pas nécessairement distinct). S'il y a moins de k niveaux dans l'arbre, renvoyez -1.

Notez que deux nœuds sont au même niveau s'ils ont la même distance de la racine.

Exemple 1 :

• Entrée : racine = [5,8,9,2,1,3,7,4,6], k = 2
• Sortie : 13
• Explication : Les sommes de niveaux sont les suivantes :
  • Niveau 1 : 5.
  • Niveau 2 : 8 9 = 17.
  • Niveau 3 : 2 1 3 7 = 13.
  • Niveau 4 : 4 6 = 10.
  • La 2^ème plus grande somme de niveau est 13.

Exemple 2 :

• Entrée : root = [1,2,null,3], k = 1
• Sortie : 3
• Explication : La plus grande somme de niveaux est 3.

Contraintes :

• Le nombre de nœuds dans l'arbre est n.
• 2 <= n <= 10⁵
• 1 <= Node.val <= 10⁶
• 1 <= k <= n

Indice :

1. Trouvez la somme des valeurs des nœuds à chaque niveau et renvoyez le kième plus grand.
2. Pour trouver la somme des valeurs des nœuds à chaque niveau, vous pouvez utiliser un algorithme DFS ou BFS pour parcourir l'arborescence et suivre le niveau de chaque nœud.

Solution :

Nous suivrons ces étapes :

1. Traversée d'ordre de niveau : Nous utiliserons une recherche en largeur d'abord (BFS) pour parcourir l'arborescence niveau par niveau.
2. Calculer les sommes de niveaux : pendant le parcours BFS, nous calculerons la somme des valeurs de nœuds à chaque niveau.
3. Trier et trouver la k-ème plus grande somme : Après avoir calculé les sommes pour tous les niveaux, nous trierons les sommes et récupérerons la k-ème plus grande valeur.

Implémentons cette solution en PHP : 2583. Kième plus grande somme dans un arbre binaire

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

/**
 * @param TreeNode $root
 * @param Integer $k
 * @return Integer
 */
function kthLargestLevelSum($root, $k) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example 1:
// Input: root = [5,8,9,2,1,3,7,4,6], k = 2
$root1 = new TreeNode(5);
$root1->left = new TreeNode(8);
$root1->right = new TreeNode(9);
$root1->left->left = new TreeNode(2);
$root1->left->right = new TreeNode(1);
$root1->right->left = new TreeNode(3);
$root1->right->right = new TreeNode(7);
$root1->left->left->left = new TreeNode(4);
$root1->left->left->right = new TreeNode(6);
echo kthLargestLevelSum($root1, 2); // Output: 13

// Example 2:
// Input: root = [1,2,null,3], k = 1
$root2 = new TreeNode(1);
$root2->left = new TreeNode(2);
$root2->left->left = new TreeNode(3);
echo kthLargestLevelSum($root2, 1); // Output: 3
?>





  
  
  Explication:



Classe TreeNode : Nous définissons la classe TreeNode pour représenter un nœud dans l'arbre binaire, où chaque nœud a une valeur (val), un enfant gauche (gauche) et un enfant droit (à droite).
BFS Traversal : La fonction kthLargestLevelSum utilise une file d'attente pour effectuer une traversée BFS. Pour chaque niveau, nous additionnons les valeurs des nœuds et stockons le résultat dans un tableau ($levelSums).
Tri des sommes de niveau : Après avoir parcouru tout l'arbre et calculé les sommes de niveau, nous trions les sommes par ordre décroissant à l'aide de rsort. Cela nous permet d'accéder facilement à la k-ème plus grosse somme.
Edge Case Handling : S'il y a moins de k niveaux, nous renvoyons -1.



  
  
  Complexité temporelle :




BFS Traversal : O(n), où n est le nombre de nœuds dans l'arborescence.

Tri : O(m log m), où m est le nombre de niveaux dans l'arborescence. Puisque m est beaucoup plus petit que n, le tri est relativement rapide.
Complexité temporelle globale : O(n m log m).



  
  
  Complexité spatiale :




Queue : O(n), pour stocker les nœuds pendant BFS.

Sommes de niveaux : O(m), pour stocker la somme de chaque niveau.
Complexité spatiale globale : O(n).


Cette approche garantit que nous parcourons l'arbre efficacement et renvoyons la bonne kième la plus grande somme de niveau.

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!