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:
Beispiel 2:
Beispiel 3:
Einschränkungen:
Hinweis:
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:
Lassen Sie uns diese Lösung in PHP implementieren: 1367. Verknüpfte Liste im Binärbaum
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:
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.
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:
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:
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!