Hauteur de l'arbre binaire après les requêtes de suppression de sous-arbre

2458. Hauteur de l'arbre binaire après les requêtes de suppression de sous-arbre

Difficulté : Difficile

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

On vous donne la racine d'un arbre binaire à n nœuds. Chaque nœud se voit attribuer une valeur unique de 1 à n. Vous recevez également un tableau de requêtes de taille m.

Vous devez effectuer m indépendantes requêtes sur l'arborescence où dans la i^ième requête vous faites ce qui suit :

• Supprimez le sous-arbre enraciné au nœud avec la valeur querys[i] de l'arborescence. Il est garanti que les requêtes[i] ne seront pas égales à la valeur de la racine.

Renvoyer un tableau de réponse de taille m où réponse[i] est la hauteur de l'arbre après avoir effectué la i^ième requête.

Remarque :

• Les requêtes sont indépendantes, l'arbre revient donc à son état initial après chaque requête.
• La hauteur d'un arbre est le nombre d'arêtes dans le chemin simple le plus long de la racine à un nœud de l'arbre.

Exemple 1 :

• Entrée : root = [1,3,4,2,null,6,5,null,null,null,null,null,7], requêtes = [4]
• Sortie : [2]
• Explication : Le diagramme ci-dessus montre l'arborescence après avoir supprimé le sous-arbre enraciné au nœud avec la valeur 4.
  • La hauteur de l'arbre est de 2 (Le chemin 1 -> 3 -> 2).

Exemple 2 :

• Entrée : racine = [5,8,9,2,1,3,7,4,6], requêtes = [3,2,4,8]
• Sortie : [3,2,3,2]
• Explication : Nous avons les requêtes suivantes :
  • Suppression du sous-arbre enraciné au nœud de valeur 3. La hauteur de l'arbre devient 3 (Le chemin 5 -> 8 -> 2 -> 4).
  • Suppression du sous-arbre enraciné au nœud de valeur 2. La hauteur de l'arbre devient 2 (Le chemin 5 -> 8 -> 1).
  • Suppression du sous-arbre enraciné au nœud de valeur 4. La hauteur de l'arbre devient 3 (Le chemin 5 -> 8 -> 2 -> 6).
  • Suppression du sous-arbre enraciné au nœud de valeur 8. La hauteur de l'arbre devient 2 (Le chemin 5 -> 9 -> 3).

Contraintes :

• Le nombre de nœuds dans l'arbre est n.
• 2 <= n <= 10⁵
• 1 <= Node.val <= n
• Toutes les valeurs de l'arbre sont uniques.
• m == requêtes.longueur
• 1 <= m <= min(n, 10⁴)
• 1 <= requêtes[i] <= n
• requêtes[i] != root.val

Indice :

1. Essayez de pré-calculer la réponse pour chaque nœud de 1 à n et répondez à chaque requête en O(1).
2. Les réponses peuvent être précalculées en un seul parcours d'arbre après avoir calculé la hauteur de chaque sous-arbre.

Solution :

La solution utilise une approche en deux passes :

1. Calculez la hauteur de chaque nœud dans l'arbre.
2. Déterminez la hauteur maximale de l'arbre après avoir supprimé le sous-arbre enraciné à chaque nœud interrogé.

Implémentons cette solution en PHP : 2458. Hauteur de l'arbre binaire après les requêtes de suppression de sous-arbre

Répartition du code

1. Définition et propriétés de la classe :

class Solution {

    private $valToMaxHeight = [];
    private $valToHeight = [];

• valToMaxHeight : ce tableau stockera la hauteur maximale de l'arborescence après avoir supprimé le sous-arbre de chaque nœud.
• valToHeight : ce tableau stockera la hauteur du sous-arbre de chaque nœud.

2. Fonction principale :

function treeQueries($root, $queries) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

• La fonction treeQueries prend la racine de l'arbre et le tableau des requêtes.
• Il appelle d'abord la fonction height pour calculer la hauteur de chaque nœud.
• Ensuite, il appelle la fonction dfs (recherche en profondeur) pour calculer les hauteurs maximales après la suppression des sous-arbres.
• Enfin, il remplit le tableau de réponses avec les résultats de chaque requête.

3. Calcul de la hauteur :

private function height($node) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

• Cette fonction calcule la hauteur de chaque nœud de manière récursive.
• Si le nœud est nul, il renvoie 0.
• Si la hauteur du nœud est déjà calculée, il la récupère du cache (valToHeight).
• Il calcule la hauteur en fonction des hauteurs de ses enfants gauche et droit et la stocke dans valToHeight.

4. Recherche en profondeur d'abord de la hauteur maximale :

private function dfs($node, $depth, $maxHeight) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

• Cette fonction effectue un DFS pour calculer la hauteur maximale de l'arbre après la suppression du sous-arbre de chaque nœud.
• Il enregistre la hauteur maximale actuelle dans valToMaxHeight pour le nœud actuel.
• Il calcule les hauteurs des sous-arbres gauche et droit et met à jour la hauteur maximale en conséquence.
• Il s'appelle récursivement pour les enfants gauche et droit, mettant à jour la profondeur et la hauteur maximale.

Exemple de procédure pas à pas

Passons en revue un exemple étape par étape.

Exemple d'entrée :

// Tree Structure
//        1
//       / \
//      3   4
//     /   / \
//    2   6   5
//         \
//          7

$root = [1, 3, 4, 2, null, 6, 5, null, null, null, null, null, 7];
$queries = [4];

Calcul de la hauteur initiale :

• La hauteur de l'arbre enraciné à 1 : 3
• La hauteur de l'arbre enraciné à 3 : 2
• La hauteur de l'arbre enraciné à 4 : 2 (hauteur des sous-arbres enracinés à 6 et 5)
• La hauteur de l'arbre enraciné à 6 : 1 (juste le nœud 7)
• La hauteur de l'arbre enraciné à 2 :0 (nœud feuille)

Après le calcul de la hauteur, valToHeight ressemblerait à ceci :

class Solution {

    private $valToMaxHeight = [];
    private $valToHeight = [];

DFS pour les hauteurs maximales :

• Pour la racine (1), en supprimant le sous-arbre 4 feuilles :
  • Hauteur gauche : 2 (enraciné à 3)
  • Hauteur droite : 1 (enraciné à 5)
• Ainsi, la hauteur maximale après avoir supprimé 4 est de 2.

Tableau de résultats après requêtes :

• Pour la requête 4, le résultat serait [2].

Résultat final

Le résultat de l'entrée fournie sera :

function treeQueries($root, $queries) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

Cette approche structurée garantit que nous calculons efficacement les hauteurs nécessaires et répondons à chaque requête en temps constant après le prétraitement initial. La complexité globale est O(n m), où n est le nombre de nœuds dans l'arbre et m est le nombre de requêtes.

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!