Maison > développement back-end > tutoriel php > Hauteur de l'arbre binaire après les requêtes de suppression de sous-arbre

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

Barbara Streisand
Libérer: 2024-11-03 08:57:02
original
383 Les gens l'ont consulté

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 iiè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 iiè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 :

Height of Binary Tree After Subtree Removal Queries

  • 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 :

Height of Binary Tree After Subtree Removal Queries

  • 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 <= 105
  • 1 <= Node.val <= n
  • Toutes les valeurs de l'arbre sont uniques.
  • m == requêtes.longueur
  • 1 <= m <= min(n, 104)
  • 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 = [];
Copier après la connexion
Copier après la connexion
  • 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
     */
}
Copier après la connexion
Copier après la connexion
  • 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
     */
}
Copier après la connexion
  • 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
     */
}
Copier après la connexion
  • 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];
Copier après la connexion

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 = [];
Copier après la connexion
Copier après la connexion

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
     */
}
Copier après la connexion
Copier après la connexion

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!

Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Derniers articles par auteur
Tutoriels populaires
Plus>
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal