Path Sum

Q: Wie hoch ist die Zeitkomplexität von Path Sum?

O(n) : Jeder Knoten wird höchstens einmal besucht, und die Suche kann beim ersten passenden Blattknoten beendet werden. Der zusätzliche Speicherbedarf beträgt O(h) für den untersuchten Pfad, entweder als Aufrufrahmen oder als Einträge auf deinem eigenen Stack.

LeichtBaumdurchlauf

+10

Du erhältst einen Binärbaum, der im Level-Order-Verfahren im Array tree gespeichert ist, und eine Zahl targetSum. Die Wurzel befindet sich am Index 0, die Kinder des Knotens am Index i befinden sich bei 2*i+1 (links) und 2*i+2 (rechts), -1 kennzeichnet eine leere Stelle, und das Array kann mit zusätzlichen -1-Einträgen enden. Gib true zurück, wenn ein Pfad von der Wurzel abwärts zu einem Blatt Werte enthält, deren Summe targetSum ergibt, andernfalls false. Ein Blatt ist ein Knoten, dessen beide Kinderstellen leer sind.

Funktion

hasPathSum(tree: integer-array, targetSum: integer) → boolean

treeinteger-array: der Binärbaum in Level-Reihenfolge, mit -1 für eine leere Stelle
targetSuminteger: die Summe, die ein Pfad von der Wurzel zu einem Blatt erreichen muss
Gibt zurückboolean: true, wenn ein Pfad von der Wurzel zu einem Blatt die Summe targetSum ergibt, andernfalls false

Einschränkungen

1 ≤ tree.length ≤ 32767
Jedes tree[i] ist -1 oder ein Wert mit 0 ≤ tree[i] ≤ 1000.
tree[0] ist niemals -1, also hat der Baum mindestens einen Knoten.
Das Array kann nach dem letzten Knoten noch zusätzliche -1-Einträge enthalten.
Beide Kinder einer leeren Stelle sind ebenfalls leer, und die Tiefe beträgt höchstens 14.
0 ≤ targetSum ≤ 15000

Beispiele

Eingabe: tree = [3, 9, 6, -1, 2, 1, 7]targetSum = 14
Ausgabe: true
Erklärung: Der Pfad 3, 9, 2 (Indizes 0, 1, 4) ergibt zusammen 14, und die 2 am Index 4 ist ein Blatt.

Eingabe: tree = [3, 9, 6, -1, 2, 1, 7]targetSum = 12
Ausgabe: false
Erklärung: 3 + 9 = 12, aber die 9 hat ein Kind, daher endet dort kein Pfad. Die drei Pfade von der Wurzel zu einem Blatt ergeben 14, 10 und 16, und keiner davon ist 12.

Eingabe: tree = [4, -1, -1]targetSum = 4
Ausgabe: true
Erklärung: Beide Kindpositionen der Wurzel sind leer, also ist die Wurzel selbst ein Blatt. Der Pfad, der nur 4 enthält, ergibt zusammen 4.

Weiterführende Frage

Kannst du die Pfade zählen, deren Summe targetSum ergibt, wenn ein Pfad an einem beliebigen Knoten beginnen und an einem beliebigen darunterliegenden Knoten enden darf?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Es zählen nur vollständige Pfade, von der Wurzel bis hinunter zu einem Blatt. Eine laufende Summe kann an einem Knoten, der noch Kinder hat, targetSum erreichen; das zählt nicht. Gib daher die Summe des Pfads an jeden Knoten weiter, als Parameter oder auf einem Stack, und vergleiche sie nur an Blättern mit dem Ziel.

Rekursion über die verbleibende Summe

Idee

Ein Pfad, dessen Summe targetSum ergibt, beginnt mit dem Wert der Wurzel. Der Rest des Pfads, der bei einem der Kinder der Wurzel beginnt, muss also die Summe targetSum minus diesem Wert ergeben. Das ist dieselbe Frage für einen kleineren Baum. Ziehe auf dem Weg nach unten den Wert jedes Knotens ab; bei einem Blatt endet der Pfad, die Antwort lautet also, ob nichts übrig ist.

Im ersten Beispiel bleiben bei der Wurzel 14 - 3 = 11 übrig, bei der 9 bleiben 2 übrig und beim Blatt 2 bleibt 0 übrig. Im zweiten bleibt bei der 9 bereits 0 übrig, sie hat aber ein Kind, daher wird die Suche fortgesetzt. Jeder Knoten wird einmal besucht, also beträgt die Laufzeit O(n), und der Aufrufstapel enthält pro Ebene einen Frame, höchstens 15.

Algorithmus

Schreibe walk(i, remaining) und ziehe tree[i] von remaining ab.
Wenn beide Kindpositionen von i leer sind (Index hinter dem Ende oder -1), gib zurück, ob remaining 0 ist.
Gib andernfalls true zurück, wenn walk bei einem tatsächlichen linken Kind oder bei einem tatsächlichen rechten Kind true zurückgibt.
Gib walk(0, targetSum) zurück.

def hasPathSum(tree, targetSum):
    n = len(tree)

    def walk(i, remaining):
        # remaining is what the path still needs once it reaches node i.
        remaining -= tree[i]
        left, right = 2 * i + 1, 2 * i + 2
        has_left = left < n and tree[left] != -1
        has_right = right < n and tree[right] != -1
        if not has_left and not has_right:
            return remaining == 0  # a leaf: the path ends here
        return (has_left and walk(left, remaining)) or (has_right and walk(right, remaining))

    return walk(0, targetSum)

Tiefensuche mit einem expliziten Stapel

Idee

Bei der Rekursion wird pro Aufruf eine Zahl gespeichert. Speichere sie stattdessen selbst auf einem Stack neben jedem Knoten: die Summe des Pfads von der Wurzel bis zu diesem Knoten. Beginne mit (0, tree[0]); jedes Kind erhält die Summe seines Elternknotens plus seinen eigenen Wert. Entferne ein Paar vom Stack. Wenn der Knoten ein Blatt mit der Summe targetSum ist, bist du fertig; andernfalls füge seine tatsächlichen Kinder hinzu.

Jeder echte Knoten wird einmal hinzugefügt: Zeitaufwand O(n), und der Stack enthält ungefähr ein wartendes Geschwister pro Ebene: O(h). Dieselbe Schleife funktioniert auch bei einem tiefen, zeigerbasierten Baum, bei dem der Rekursionsstack erschöpft sein könnte.

Algorithmus

Lege (0, tree[0]) auf einen Stack.
Nimm ein Paar (i, total) vom Stack und prüfe die Kindpositionen 2*i+1 und 2*i+2.
Wenn keines der beiden Kinder tatsächlich existiert und total gleich targetSum ist, gib true zurück.
Lege jedes tatsächlich existierende Kind c als (c, total + tree[c]) auf den Stack.
Wenn der Stack leer ist, gib false zurück.

def hasPathSum(tree, targetSum):
    n = len(tree)
    stack = [(0, tree[0])]  # (node index, sum of the path from the root to it)
    while stack:
        i, total = stack.pop()
        left, right = 2 * i + 1, 2 * i + 2
        has_left = left < n and tree[left] != -1
        has_right = right < n and tree[right] != -1
        if not has_left and not has_right and total == targetSum:
            return True  # a leaf whose path adds up
        if has_left:
            stack.append((left, total + tree[left]))
        if has_right:
            stack.append((right, total + tree[right]))
    return False

Stolperfallen und Grenzfälle

Vergleiche die Summe an jedem Knoten. Im zweiten Beispiel ergibt 3 + 9 = 12 beim 9 eine Übereinstimmung. Dieser Knoten hat ein Kind, daher lautet die Antwort false.
Lass einen leeren Kindplatz einen Pfad beenden. Dann endet das 9 im zweiten Beispiel über seinen leeren linken Platz einen Pfad.
Vergiss nicht die Wurzel allein. Ein einzelner Knoten ist ein Blatt, daher ist [4] mit dem Zielwert 4 true, und ebenso [0] mit dem Zielwert 0.
Lies nicht über das Ende des Arrays hinaus. Ein Blatt nahe dem Ende kann Kindindizes haben, die hinter dem letzten Eintrag liegen.
Verwechsle nicht den Offset in Lua und R. Behalte die 0-basierte Indizierung der Knoten für 2*i+1 bei und lies tree[i + 1].

Häufige Fragen3

Wie hoch ist die Zeitkomplexität von Path Sum?

O(n): Jeder Knoten wird höchstens einmal besucht, und die Suche kann beim ersten passenden Blattknoten beendet werden. Der zusätzliche Speicherbedarf beträgt O(h) für den untersuchten Pfad, entweder als Aufrufrahmen oder als Einträge auf deinem eigenen Stack.

Kann Path Sum mit BFS gelöst werden?

Ja. Lege Paare aus einem Knoten und seiner Pfadsumme in eine Warteschlange statt in einen Stapel und prüfe jedes Blatt, sobald es herauskommt. Der Zeitaufwand beträgt weiterhin O(n), aber die Warteschlange kann eine ganze Ebene aufnehmen, etwa die Hälfte der Knoten eines vollständigen Baums, während ein Stapel etwa einen Knoten pro Ebene enthält.

Wie findest du jeden Pfad, dessen Summe dem Ziel entspricht?

Führe die Liste der Knoten auf dem aktuellen Pfad beim Abstieg mit, kopiere sie an jedem Blatt, dessen Summe übereinstimmt, in die Antwort und entferne beim Zurückgehen den letzten Knoten. Die Traversierung bleibt gleich. Das Kopieren der Pfade kann mehr kosten als die Traversierung, wenn viele Blätter übereinstimmen.

def hasPathSum(tree, targetSum):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argumente

tree = [3, 9, 6, -1, 2, 1, 7]
targetSum = 14

Erwartete Ausgabe

true