Verknüpfte Liste im Binärbaum

1367. Verknüpfte Liste im Binärbaum

Schwierigkeit:Mittel

Themen: Verknüpfte Liste, Baum, Tiefensuche, Breitensuche, Binärbaum

Gegeben sei eine Binärbaumwurzel und eine verknüpfte Liste mit Kopf als erstem Knoten.

Gib „True“ zurück, wenn alle Elemente in der verknüpften Liste beginnend mit dem Kopf einem Abwärtspfad entsprechen, der im Binärbaum verbunden ist, andernfalls False zurückgeben.

In diesem Zusammenhang bedeutet Abwärtspfad einen Pfad, der an einem Knoten beginnt und nach unten führt.

Beispiel 1:

• Eingabe: head = [4,2,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null ,1,3]
• Ausgabe:wahr
• Erklärung:Knoten in Blau bilden einen Unterpfad im Binärbaum.

Beispiel 2:

• Eingabe: head = [1,4,2,6], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null ,null,1,3]
• Ausgabe:wahr

Beispiel 3:

• Eingabe: head = [1,4,2,6,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null ,null,null,1,3]
• Ausgabe:falsch
• Erklärung:Es gibt keinen Pfad im Binärbaum, der alle Elemente der verknüpften Liste ab Kopf enthält.

Einschränkungen:

• Die Anzahl der Knoten im Baum liegt im Bereich [1, 2500].
• Die Anzahl der Knoten in der Liste liegt im Bereich [1, 100].
• 1

Hinweis:

1. Erstellen Sie eine rekursive Funktion anhand eines Zeigers in einer verknüpften Liste und eines beliebigen Knotens im Binärbaum. Überprüfen Sie, ob alle Elemente in der verknüpften Liste, beginnend mit dem Kopf, einem Abwärtspfad im Binärbaum entsprechen.

Lösung:

Wir müssen rekursiv prüfen, ob eine verknüpfte Liste mit einem Abwärtspfad in einem Binärbaum übereinstimmen kann. Wir verwenden die Tiefensuche (DFS), um den Binärbaum zu erkunden und zu versuchen, die verknüpfte Liste vom Kopf bis zu den Blattknoten abzugleichen.

So können wir die Lösung angehen:

Schritte:

1. Rekursive Funktion zur Übereinstimmung mit verknüpften Listen: Erstellen Sie eine Hilfsfunktion, die einen verknüpften Listenknoten und einen Baumknoten akzeptiert. Diese Funktion prüft, ob die verknüpfte Liste ausgehend vom aktuellen Knoten mit einem Abwärtspfad im Binärbaum übereinstimmt.
2. DFS durch den Baum: Durchlaufen Sie den Binärbaum mit DFS und prüfen Sie an jedem Knoten, ob es eine Übereinstimmung ab diesem Knoten gibt.
3. Grundbedingungen: Die Rekursion sollte anhalten und „true“ zurückgeben, wenn die verknüpfte Liste vollständig durchlaufen wurde, und „false“ zurückgeben, wenn der Binärbaumknoten null ist oder die Werte nicht übereinstimmen.
4. Suche an jedem Knoten starten: Beginnen Sie mit der Übereinstimmungsprüfung an jedem Baumknoten, um potenzielle Startpunkte für die verknüpfte Liste zu finden.

Lassen Sie uns diese Lösung in PHP implementieren: 1367. Verknüpfte Liste im Binärbaum

<?php // Definition for a singly-linked list node.
class ListNode {
    public $val = 0;
    public $next = null;
    function __construct($val = 0, $next = null) {
        $this->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
?>

Erläuterung:

1. isSubPath($head, $root):

   • Diese Funktion prüft rekursiv, ob die verknüpfte Liste, die bei $head beginnt, einem Abwärtspfad im Baum entspricht.
   • Es prüft zunächst, ob der aktuelle Wurzelknoten der Anfang der Liste ist (durch Aufruf von dfs).
   • Wenn nicht, werden die linken und rechten Teilbäume rekursiv durchsucht.

2. dfs($head, $root):

   • Diese Hilfsfunktion prüft, ob die verknüpfte Liste mit dem Baum übereinstimmt, beginnend beim aktuellen Baumknoten.
   • Wenn die Liste vollständig durchlaufen ist ($head === null), wird true zurückgegeben.
   • Wenn der Baumknoten null ist oder die Werte nicht übereinstimmen, wird „false“ zurückgegeben.
   • Andernfalls werden weiterhin die linken und rechten Kinder überprüft.

Beispielausführung:

Für die Eingabe head = [4,2,8] und root = [1,4,4,null,2,2,null,1,null,6,8] wird der Algorithmus:

• Beginnen Sie bei der Wurzel (Knoten 1), keine Übereinstimmung.
• Gehe zum linken untergeordneten Knoten (Knoten 4), kombiniere 4, gehe dann nach unten und kombiniere 2, dann kombiniere 8 und gib true zurück.

Komplexität:

• Zeitkomplexität: O(N * min(L, H)), wobei N die Anzahl der Knoten im Binärbaum, L die Länge der verknüpften Liste und H die Höhe der Binärdatei ist Baum.
• Raumkomplexität: O(H) aufgrund der Rekursionstiefe des Binärbaums.

Diese Lösung prüft mithilfe von DFS effizient auf den Unterpfad im Binärbaum.

Kontaktlinks

Wenn Sie diese Serie hilfreich fanden, denken Sie bitte darüber nach, dem Repository einen Stern auf GitHub zu geben oder den Beitrag in Ihren bevorzugten sozialen Netzwerken zu teilen? Ihre Unterstützung würde mir sehr viel bedeuten!

Wenn Sie weitere hilfreiche Inhalte wie diesen wünschen, folgen Sie mir gerne:

• LinkedIn
• GitHub

Das obige ist der detaillierte Inhalt vonVerknüpfte Liste im Binärbaum. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!