Liste chaînée dans l'arborescence binaire

1367. Liste chaînée dans l'arbre binaire

Difficulté :Moyen

Sujets : Liste chaînée, arbre, recherche en profondeur d'abord, recherche en largeur d'abord, arbre binaire

Étant donné une racine d'arbre binaire et une liste chaînée avec head comme premier nœud.

Renvoyer True si tous les éléments de la liste chaînée à partir de la tête correspondent à un chemin descendant connecté dans l'arbre binaire sinon renvoyer False.

Dans ce contexte, un chemin descendant signifie un chemin qui commence à un nœud et descend.

Exemple 1 :

• Entrée : head = [4,2,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null ,1,3]
• Sortie : vrai
• Explication : Les nœuds en bleu forment un sous-chemin dans l'arbre binaire.

Exemple 2 :

• Entrée : head = [1,4,2,6], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null ,null,1,3]
• Sortie : vrai

Exemple 3 :

• Entrée : head = [1,4,2,6,8], racine = [1,4,4,null,2,2,null,1,null,6,8,null,null , nul, nul, 1,3]
• Sortie : faux
• Explication : Il n'y a aucun chemin dans l'arborescence binaire qui contient tous les éléments de la liste chaînée depuis head.

Contraintes :

• Le nombre de nœuds dans l'arborescence sera compris entre [1, 2500].
• Le nombre de nœuds dans la liste sera compris entre [1, 100].
• 1 <= Node.val <= 100 pour chaque nœud de la liste chaînée et de l'arbre binaire.

Indice :

1. Créez une fonction récursive, à partir d'un pointeur dans une liste chaînée et de n'importe quel nœud de l'arbre binaire. Vérifiez si tous les éléments de la liste chaînée à partir de la tête correspondent à un chemin descendant dans l'arbre binaire.

Solution :

Nous devons vérifier récursivement si une liste chaînée peut correspondre à un chemin descendant dans un arbre binaire. Nous utiliserons la recherche en profondeur (DFS) pour explorer l'arbre binaire et tenter de faire correspondre la liste chaînée de sa tête aux nœuds feuilles.

Voici comment nous pouvons aborder la solution :

Mesures:

1. Fonction récursive pour faire correspondre la liste chaînée : Créez une fonction d'assistance qui prend un nœud de liste chaînée et un nœud d'arborescence. Cette fonction vérifie si la liste chaînée partant du nœud actuel correspond à un chemin descendant dans l'arborescence binaire.
2. DFS à travers l'arbre : parcourez l'arbre binaire à l'aide de DFS, et à chaque nœud, vérifiez s'il y a une correspondance à partir de ce nœud.
3. Conditions de base : La récursion doit s'arrêter et renvoyer vrai si la liste chaînée est entièrement parcourue, et renvoyer faux si le nœud de l'arbre binaire est nul ou si les valeurs ne correspondent pas.
4. Démarrer la recherche à chaque nœud : commencez la vérification de correspondance à chaque nœud de l'arbre pour trouver des points de départ potentiels pour la liste chaînée.

Implémentons cette solution en PHP : 1367. Liste chaînée dans l'arbre binaire

val = $val;
        $this->next = $next;
    }
}

// Definition for a binary tree node.
class TreeNode {
    public $val = 0;
    public $left = null;
    public $right = null;
    function __construct($val = 0, $left = null, $right = null) {
        $this->val = $val;
        $this->left = $left;
        $this->right = $right;
    }
}

class Solution {

    /**
     * @param ListNode $head
     * @param TreeNode $root
     * @return Boolean
     */
    function isSubPath($head, $root) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }

    // Helper function to match the linked list starting from the current tree node.
    function dfs($head, $root) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }
}

// Example usage:

// Linked List: 4 -> 2 -> 8
$head = new ListNode(4);
$head->next = new ListNode(2);
$head->next->next = new ListNode(8);

// Binary Tree:
//      1
//     / \
//    4   4
//     \   \
//      2   2
//     / \ / \
//    1  6 8  8
$root = new TreeNode(1);
$root->left = new TreeNode(4);
$root->right = new TreeNode(4);
$root->left->right = new TreeNode(2);
$root->right->left = new TreeNode(2);
$root->left->right->left = new TreeNode(1);
$root->left->right->right = new TreeNode(6);
$root->right->left->right = new TreeNode(8);
$root->right->left->right = new TreeNode(8);

$solution = new Solution();
$result = $solution->isSubPath($head, $root);
echo $result ? "true" : "false"; // Output: true
?>





  
  
  Explication:




isSubPath($head, $root) :


Cette fonction vérifie récursivement si la liste chaînée commençant par $head correspond à un chemin descendant dans l'arborescence.
Il vérifie d'abord si le nœud racine actuel est le début de la liste (en appelant dfs).
Sinon, il recherche récursivement les sous-arbres gauche et droit.



dfs($head, $root) :


Cette fonction d'assistance vérifie si la liste chaînée correspond à l'arborescence commençant au nœud d'arborescence actuel.
Si la liste est entièrement parcourue ($head === null), elle renvoie vrai.
Si le nœud de l'arbre est nul ou si les valeurs ne correspondent pas, il renvoie false.
Sinon, il continue de vérifier les enfants gauche et droit.





  
  
  Exemple d'exécution :


Pour l'entrée head = [4,2,8] et root = [1,4,4,null,2,2,null,1,null,6,8], l'algorithme :


Commencez à la racine (nœud 1), ne parvenez pas à correspondre.
Déplacez-vous vers l'enfant de gauche (nœud 4), faites correspondre 4, puis descendez et faites correspondre 2, puis faites correspondre 8, en renvoyant vrai.



  
  
  Complexité:




Complexité temporelle : O(N * min(L, H)), où N est le nombre de nœuds dans l'arbre binaire, L est la longueur de la liste chaînée et H est la hauteur du binaire arbre.

Complexité spatiale : O(H) en raison de la profondeur de récursion de l'arbre binaire.


Cette solution vérifie efficacement le sous-chemin dans l'arborescence binaire à l'aide de DFS.

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!