Path Sum

+10

Du erhältst einen Binärbaum, der im Array tree in Ebenenreihenfolge 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 es einen Pfad von der Wurzel abwärts zu einem Blatt gibt, dessen Werte sich zu targetSum addieren, andernfalls false. Ein Blatt ist ein Knoten ohne Kinder: Beide seiner Kinderstellen sind leer.

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 bis zu einem Blatt erreichen muss
Gibt zurückboolean: wahr, wenn ein Pfad von der Wurzel zu einem Blatt die Summe targetSum ergibt, andernfalls falsch

Einschränkungen

1 ≤ tree.length ≤ 32767
Jedes tree[i] ist -1 oder ein Wert mit 0 ≤ tree[i] ≤ 1000.
tree[0] ist niemals -1, daher 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 an 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 zum 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.

+14 versteckte Tests beim Einreichen

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 kann und nicht nur von der Wurzel zu einem Blatt verläuft?

Tipps

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

0 von 3 geöffnet

Lösung

Bei der Frage geht es um vollständige Pfade, von der Wurzel bis ganz hinunter zu einem Blatt. Eine laufende Summe kann targetSum auf dem Weg nach unten bei einem Knoten erreichen, der noch Kinder hat, und das zählt nicht. Deshalb überträgst du die bisherige Pfadsumme zu jedem Knoten und vergleichst sie nur bei den Blättern mit dem Zielwert. Bei der Rekursion wird diese Summe als Parameter übergeben; bei einem Stapel wird sie neben jedem Knoten mitgeführt.

Rekursion über die verbleibende Summe

Idee

Zuerst: So bewegst du dich im Array. Der Knoten am Index i hat sein linkes Kind bei 2*i+1 und sein rechtes Kind bei 2*i+2. Ein Kind ist nur dann vorhanden, wenn sein Index innerhalb des Arrays liegt und der Wert dort nicht -1 ist. In [3, 9, 6, -1, 2, 1, 7] hat die Wurzel 3 Kinder an den Indizes 1 und 2, und bei der 9 am Index 1 ist der linke Platz bei 3 leer, während sich rechts davon die 2 am Index 4 befindet.

Nun zur Idee. Ein Pfad, dessen Werte sich zu targetSum addieren, beginnt mit dem Wert der Wurzel. Der Rest des Pfads, der bei einem der Kinder der Wurzel beginnt, muss sich also zu targetSum minus diesem Wert addieren. 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, daher lautet die Antwort dort: Ist nichts mehr übrig?

Im ersten Beispiel lässt die Wurzel 14 - 3 = 11 übrig, die 9 lässt 2 übrig, und das Blatt 2 lässt 0 übrig: true. Im zweiten Beispiel lässt die 9 bereits 0 übrig, aber sie hat ein Kind, also geht die Suche weiter, und ihr Blatt endet bei -2. Jeder Knoten wird höchstens einmal besucht: Zeitaufwand O(n). Der Aufrufstapel enthält einen Frame pro Ebene: O(h), hier höchstens 15 Frames (eine Tiefe von 14 zählt die Kanten unterhalb der Wurzel).

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.
Andernfalls gib true zurück, wenn walk für ein vorhandenes linkes oder rechtes 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 Stack

Idee

Der rekursive Aufruf speichert pro Aufruf eine Zahl: wie viel zum Ziel noch fehlt. Du kannst eine solche Zahl selbst auf einem Stack neben jedem Knoten speichern und die Aufrufe weglassen. Speichere die Summe des Pfads von der Wurzel bis zum Knoten, einschließlich des Knotens. Beginne mit (0, tree[0]) und gib jedem Kind die Summe seines Elternknotens plus seinen eigenen Wert.

Entnimm ein Paar. Wenn der Knoten ein Blatt ist und seine Summe targetSum entspricht, bist du fertig. Andernfalls lege seine tatsächlichen Kinder auf den Stack. Im ersten Beispiel wird zuerst die rechte Seite vom Stack genommen: Die Blätter 7 und 1 tragen die Summen 16 und 10. Dann wird (1, 12) für die 9 entnommen. Der Knoten ist kein Blatt, also legt er (4, 14) auf den Stack, ein Blatt mit der richtigen Summe.

Jeder tatsächliche Knoten wird einmal auf den Stack gelegt, daher beträgt die Laufzeit O(n), und die Suche endet beim ersten passenden Blatt. Der Stack enthält die wartenden Geschwister entlang des aktuellen Pfads, ungefähr eines pro Ebene, also beträgt der Speicherbedarf O(h). Dieselbe Schleife funktioniert bei einem tiefen, zeigerbasierten Baum, bei dem die Rekursion den Stack erschöpfen könnte.

Algorithmus

Lege (0, tree[0]) auf einen Stapel.
Nimm ein Paar (i, total) vom Stapel und prüfe die Positionen der Kindknoten 2*i+1 und 2*i+2.
Wenn keiner der beiden Kindknoten existiert und total gleich targetSum ist, gib true zurück.
Lege jeden existierenden Kindknoten c als (c, total + tree[c]) auf den Stapel.
Wenn der Stapel 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

Bei fast jedem Fehler in diesem Problem geht es darum, wo ein Pfad endet.

Die Summe an jedem Knoten vergleichen. Im zweiten Beispiel ergibt 3 + 9 = 12 am 9 einen Treffer. Dieser Knoten hat jedoch ein Kind, daher lautet die Antwort false. Vergleiche nur an Blättern.
Eine leere Stelle für ein Kind als Ende eines Pfads behandeln. Wenn walk an einer leeren Stelle remaining == 0 zurückgibt, zählt die 9 im zweiten Beispiel über ihre leere linke Stelle als Blatt. Ein Knoten ist nur dann ein Blatt, wenn beide Stellen leer sind.
Die Wurzel allein vergessen. Ein einzelner Knoten ist ein Blatt, daher ist [4] mit targetSum = 4 true, und [0] mit targetSum = 0 ebenfalls.
Die Suche abbrechen, sobald die Summe das Ziel überschreitet. Die Werte sind hier nie negativ, daher ist das in diesem Problem sicher. Sobald ein Baum jedoch negative Werte enthalten kann, liefert derselbe Code falsche Antworten.
Über das Ende hinaus lesen. Ein Blatt nahe dem Ende des Arrays kann Kindindizes haben, die über den letzten Eintrag hinausgehen, weil das Array direkt nach dem letzten Knoten enden kann. Prüfe den Index, bevor du tree[c] liest.
Den Versatz in Lua und R verwechseln, wo Arrays bei 1 beginnen. Behalte für die Rechnung mit 2*i+1 die nullbasierten Knotenindizes bei und lies tree[i + 1].

Häufige Fragen4

Wie hoch ist die Zeitkomplexität von Path Sum?

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

Warum prüft Path Sum die Summe nur an Blattknoten?

Das Problem fragt nach einem Pfad von der Wurzel zu einem Blatt, und ein Pfad, der an einem Knoten mit Kindern endet, ist keiner. Bei einer Überprüfung an jedem Knoten wird zu oft true zurückgegeben, zum Beispiel wenn allein der Wert der Wurzel dem Zielwert entspricht, die Wurzel aber ein Kind hat. Ein Knoten beendet einen Pfad nur dann, wenn beide seiner Kindpositionen leer sind.

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 überprüfe jedes Blatt, sobald es herausgenommen wird. Die Laufzeit beträgt weiterhin O(n), aber die Warteschlange kann eine ganze Ebene aufnehmen, also 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?

Behalte die Liste der Knoten auf dem aktuellen Pfad bei, während du nach unten gehst, kopiere sie bei jedem Blattknoten, dessen Summe übereinstimmt, in die Antwort und entferne den letzten Knoten, wenn du wieder nach oben gehst. Die Traversierung bleibt gleich; nur die Buchführung wird umfangreicher. Das Kopieren der Pfade kann mehr kosten als die Traversierung selbst, wenn viele Blattknoten übereinstimmen.

Python

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

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

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

Erwartet

true