Lowest Common Ancestor of a BST

Q: Wie hoch ist die Zeitkomplexität des niedrigsten gemeinsamen Vorfahren in einem BST?

Der Weg von der Wurzel folgt einem Pfad, benötigt also für einen Baum der Tiefe h eine Laufzeit von O(h) und zusätzlichen Speicherplatz von O(1) . Bei einem balancierten Baum sind das O(log n) ; bei einem Baum, der wie ein einzelner Pfad geformt ist, sind es O(n) .

Q: Wie unterscheidet sich der LCA in einem binären Suchbaum vom LCA in einem Binärbaum?

In einem gewöhnlichen Binärbaum kann sich ein Wert überall befinden, daher durchsuchst du beide Teilbäume jedes Knotens, und der Aufwand beträgt O(n) . In einem Suchbaum verrät dir der Vergleich der beiden Werte mit einem Knoten, auf welcher Seite sich jeder von ihnen befindet, sodass du einem einzigen Pfad von der Wurzel aus folgst. Die rekursive Methode für beliebige Bäume funktioniert zwar auch bei einem Suchbaum, aber dabei geht diese Information verloren.

Q: Kann ein Knoten sein eigener tiefster gemeinsamer Vorfahr sein?

Ja. Ein Knoten gilt als Vorfahr seiner selbst. Wenn also p über q liegt, lautet die Antwort p . Dieselbe Regel ergibt p , wenn die beiden Werte gleich sind. Der Durchlauf behandelt beide Fälle: Er endet, sobald der aktuelle Knoten einem der Werte entspricht.

Q: Warum endet der Weg am ersten Knoten, an dem sich p und q trennen?

An diesem Knoten ist ein Wert kleiner und der andere größer, also befinden sie sich in verschiedenen Teilbäumen. Jeder darunterliegende Knoten liegt nur in einem dieser Teilbäume und kann daher nicht beide enthalten. Der Verzweigungsknoten enthält beide, und kein tiefer liegender Knoten tut das – genau das ist die Definition des tiefsten gemeinsamen Vorfahren.

MittelBinärer Suchbaum

+10

Du erhältst einen binären Suchbaum, der im Array tree in Ebenenreihenfolge gespeichert ist, sowie zwei Werte p und q, die beide darin vorkommen. Die Wurzel befindet sich am Index 0, die Kinder des Knotens am Index i befinden sich an den Indizes 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. In einem binären Suchbaum ist jeder Wert im linken Teilbaum eines Knotens kleiner als der Wert des Knotens und jeder Wert in seinem rechten Teilbaum größer.

Schreibe eine Funktion namens lowestCommonAncestor, die den Wert des niedrigsten gemeinsamen Vorfahren von p und q zurückgibt: den tiefsten Knoten, der beide in seinem Teilbaum hat. Ein Knoten zählt zu seinem eigenen Teilbaum. Wenn also p über q liegt, ist die Antwort p selbst.

Funktion

lowestCommonAncestor(tree: integer-array, p: integer, q: integer) → integer

treeinteger-array: den binären Suchbaum in Ebenenreihenfolge, mit -1 für eine leere Stelle
pinteger: den ersten zu findenden Wert
qinteger: den zweiten zu findenden Wert
Gibt zurückinteger: der Wert des tiefsten Knotens, der sowohl p als auch q in seinem Teilbaum hat

Einschränkungen

1 ≤ tree.length ≤ 32767
Jedes tree[i] ist -1 oder ein Wert mit 0 ≤ tree[i] ≤ 10⁵.
tree[0] ist niemals -1, daher hat der Baum mindestens einen Knoten.
Das Array kann nach dem letzten Knoten mit zusätzlichen -1-Einträgen enden.
Beide Kinder einer leeren Stelle sind ebenfalls leer, und die Tiefe beträgt höchstens 14.
Der Baum ist ein gültiger binärer Suchbaum, daher sind alle seine Werte verschieden.
p und q sind Werte von Knoten im Baum. Sie können in beliebiger Reihenfolge auftreten und gleich sein.

Beispiele

Eingabe: tree = [20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15]p = 3q = 15
Ausgabe: 8
Erklärung: Die 3 ist das linke Kind von 8, und die 15 hängt unter 12 rechts von 8. Wenn man von beiden aus nach oben steigt, ist der erste Knoten, den beide erreichen, 8; das ist also die Antwort. Die Wurzel 20 ist ebenfalls ein gemeinsamer Vorfahr, liegt aber höher.

Eingabe: tree = [20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15]p = 12q = 10
Ausgabe: 12
Erklärung: Die 10 ist das linke Kind von 12. Ein Knoten zählt als sein eigener Vorfahr, daher enthält der Teilbaum von 12 beide Werte, und kein darunterliegender Knoten enthält sie: Die Antwort ist 12. Die Werte können in beliebiger Reihenfolge vorkommen; hier ist p der größere.

Eingabe: tree = [50, 30, 70, 20, 40, 60, 80, -1, -1, -1, -1, 55]p = 55q = 80
Ausgabe: 70
Erklärung: Sowohl 55 als auch 80 sind größer als die Wurzel 50, daher befinden sie sich beide rechts davon. Bei 70 trennen sich ihre Wege: 55 ist kleiner und befindet sich links (unterhalb von 60), 80 ist größer und befindet sich rechts. Daher ist 70 die Antwort.

+12 versteckte Tests beim Einreichen

Weiterführende Frage

Was würdest du ändern, wenn p oder q möglicherweise im Baum fehlen und die Funktion in diesem Fall -1 zurückgeben müsste?

Tipps

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

0 von 3 geöffnet

Lösung

In einem gewöhnlichen Binärbaum kannst du nicht feststellen, wo sich ein Wert befindet, ohne beide Seiten jedes Knotens zu durchsuchen. Ein Suchbaum zeigt dir an jedem Knoten: Kleinere Werte liegen links, größere rechts. Beginne also an der Wurzel und gehe zu der Seite, auf der sich beide Werte befinden. Der erste Knoten, an dem sie nicht mehr auf derselben Seite liegen, ist die Antwort. Du findest ihn, indem du einem einzigen Pfad folgst und den Rest des Baums nie betrachtest.

Den gesamten Baum durchsuchen und die Reihenfolge ignorieren

Idee

Zuerst: Wie bewegt man sich im Array? Der Knoten am Index i hat sein linkes Kind am Index 2*i+1 und sein rechtes Kind am Index 2*i+2. Ein Kind existiert nur, wenn sein Index innerhalb des Arrays liegt und der Wert dort nicht -1 ist. In [20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15] hat die Wurzel 20 die Werte 8 und 31 an den Indizes 1 und 2, und der Wert 12 an Index 4 hat 10 und 15 an den Indizes 9 und 10.

Diese erste Methode funktioniert mit jedem binären Baum. Ein rekursives find(i) gibt an, was der Teilbaum an Position i enthält. Eine leere Stelle gibt -1 zurück. Ein Knoten mit dem Wert p oder q gibt sich selbst zurück: Entweder liegt der andere Wert darunter, und dann ist er die Antwort, oder der andere Wert befindet sich an anderer Stelle, und ein weiter oben liegender Knoten wird beide sehen. Andernfalls fragt der Knoten beide Kinder ab. Wenn beide Seiten etwas zurückgeben, liegt p auf der einen Seite und q auf der anderen, also treffen sie sich an diesem Knoten. Wenn nur eine Seite etwas zurückgibt, wird dieser Wert nach oben weitergegeben.

Für p = 3 und q = 15 erhält der Knoten 8 den Index 3 von links und den Index 10 von rechts und gibt sich daher selbst zurück. Die Wurzel erhält diesen Wert von links und -1 von rechts und gibt 8 nach oben weiter.

Die Methode ist korrekt, besucht aber möglicherweise jeden Knoten: Laufzeit O(n), mit O(h) für die Rekursion. Sie nutzt niemals die Reihenfolge der Werte, und genau darum geht es bei einem Suchbaum.

Algorithmus

Schreibe find(i). Wenn die Stelle bei i leer ist (hinter dem Ende oder -1), gib -1 zurück.
Wenn tree[i] p oder q ist, gib i zurück.
Rufe find für 2*i+1 und 2*i+2 auf. Wenn beide etwas gefunden haben, gib i zurück.
Andernfalls gib die Seite zurück, die etwas gefunden hat, oder -1.
Gib tree[find(0)] zurück.

def lowestCommonAncestor(tree, p, q):
    n = len(tree)

    def find(i):
        # In the subtree at index i: the index of the answer if both values are
        # inside, the index of the one that is, or -1 when neither is.
        if i >= n or tree[i] == -1:
            return -1
        if tree[i] == p or tree[i] == q:
            return i
        left = find(2 * i + 1)
        right = find(2 * i + 2)
        if left != -1 and right != -1:
            return i  # one value on each side: this node is the answer
        return left if left != -1 else right

    return tree[find(0)]

Vergleiche die beiden Suchpfade

Idee

Nutze nun die Ordnung. Du kannst einen Wert so finden, wie ein Suchbaum durchsucht werden soll: Beginne an der Wurzel, gehe nach links, wenn der Wert kleiner als der Knoten ist, nach rechts, wenn er größer ist, und halte an, wenn du ihn gefunden hast. Dieser Weg führt durch alle Vorfahren des Werts und durch nichts anderes, denn der Pfad von der Wurzel zu einem Knoten ist eindeutig.

Halte den Weg für p und den Weg für q fest. Beide beginnen an der Wurzel und folgen denselben Knoten, bis die Werte unterschiedliche Wege einschlagen. Der gemeinsame Anfang ist die Liste ihrer gemeinsamen Vorfahren, daher ist der letzte gemeinsame Wert der niedrigste. Für 3 und 15 lauten die Pfade 20, 8, 3 und 20, 8, 12, 15: Sie haben 20, 8 gemeinsam, und die Antwort ist 8. Für 12 und 10 lauten sie 20, 8, 12 und 20, 8, 12, 10, und die Antwort ist 12.

Jeder Weg benötigt einen Schritt pro Ebene, daher beträgt die Laufzeit O(h), hier höchstens 14 Schritte, unabhängig davon, wie viele Knoten der Baum enthält. Die beiden Listen benötigen O(h) Speicherplatz.

Algorithmus

Schreibe path(target): Beginne bei Index 0, speichere tree[i], stoppe, wenn der Wert target entspricht, andernfalls gehe zu 2*i+1, wenn target kleiner ist, und zu 2*i+2, wenn der Wert größer ist.
Erstelle den Pfad zu p und den Pfad zu q.
Gehe beide Listen vom Anfang an durch, solange ihre Werte übereinstimmen, und merke dir die letzte Übereinstimmung.
Gib den letzten gemeinsamen Wert zurück.

def lowestCommonAncestor(tree, p, q):
    def path(target):
        # The values met on the way from the root down to target.
        values = []
        i = 0
        while True:
            values.append(tree[i])
            if tree[i] == target:
                return values
            i = 2 * i + 1 if target < tree[i] else 2 * i + 2

    to_p, to_q = path(p), path(q)
    # Both paths start at the root; the answer is the last value they share.
    answer = to_p[0]
    for a, b in zip(to_p, to_q):
        if a != b:
            break
        answer = a
    return answer

Gehe nach unten, bis sich die Werte aufteilen

Idee

Die beiden Pfade stimmen so lange überein, wie p und q in dieselbe Richtung gehen, daher musst du sie nicht speichern. Gehe beide gleichzeitig entlang. An einem Knoten mit dem Wert v: Sind beide Werte kleiner als v, liegen beide im linken Teilbaum, und das gilt auch für jeden gemeinsamen Vorfahren unterhalb von v: Gehe nach links. Sind beide größer, gehe nach rechts.

Andernfalls bist du angekommen. Entweder ist ein Wert kleiner als v und der andere größer, sodass sie in verschiedenen Teilbäumen liegen und kein Kind von v beide enthält; oder einer der Werte entspricht v, und ein Knoten ist sein eigener Vorfahr. In beiden Fällen ist v der tiefste Knoten oberhalb beider.

Im dritten Beispiel ist die Wurzel 50 kleiner als 55 und 80, also gehst du nach rechts zu 70. Dort ist 55 kleiner und 80 größer: Die Antwort ist 70. Im zweiten Beispiel gehst du von 20 zu 8 und dann zu 12, was p entspricht, und hältst an.

Du folgst einem einzigen Pfad von der Wurzel aus und führst pro Ebene einen Vergleich beider Werte durch. Daher beträgt die Laufzeit O(h) und der Speicherbedarf O(1). Der Rest des Baums wird nie gelesen.

Algorithmus

Beginne bei Index i = 0.
Lies v = tree[i].
Wenn p < v und q < v, gehe zu 2*i+1 und wiederhole den Vorgang.
Wenn p > v und q > v, gehe zu 2*i+2 und wiederhole den Vorgang.
Gib andernfalls v zurück.

def lowestCommonAncestor(tree, p, q):
    i = 0  # start at the root
    while True:
        value = tree[i]
        if p < value and q < value:
            i = 2 * i + 1  # both are smaller: the answer is on the left
        elif p > value and q > value:
            i = 2 * i + 2  # both are larger: the answer is on the right
        else:
            return value  # they split here, or one of them is this node

Stolperfallen und Grenzfälle

Der Durchlauf ist kurz, daher entstehen die meisten Fehler durch die Abbruchregel.

Verwendung von ≤ und ≥ in den Prüfungen für die Schritte. Bei p = 12 und q = 10 geht der Test p ≤ 12 und q ≤ 12 über die Antwort hinaus bis zu 10, und von dort gibt der Durchlauf 10 zurück oder läuft aus dem Baum heraus. Gehe nur dann weiter, wenn beide Werte strikt auf derselben Seite liegen.
Annahme, dass p < q gilt. Die Werte können in beliebiger Reihenfolge vorkommen. Vergleiche beide mit dem Knoten oder vertausche sie zuerst, sodass p der kleinere Wert ist.
Vergessen, dass einer der Werte ein Vorfahr des anderen sein kann. Dann ist dieser Wert selbst die Antwort, nicht sein Elternknoten.
Den Index statt des Werts zurückgeben. Die Funktion gibt tree[i] zurück, nicht i.
Den gesamten Baum durchsuchen. Das ergibt zwar die richtige Antwort, besucht aber möglicherweise jeden Knoten, obwohl ein einziger Pfad genügt.
Den Versatz in Lua und R verwechseln, wo Arrays bei 1 beginnen. Behalte die Knotenindizes für die Berechnung 2*i+1 bei 0 bei und lies tree[i + 1].

Häufige Fragen4

Wie hoch ist die Zeitkomplexität des niedrigsten gemeinsamen Vorfahren in einem BST?

Der Weg von der Wurzel folgt einem Pfad, benötigt also für einen Baum der Tiefe h eine Laufzeit von O(h) und zusätzlichen Speicherplatz von O(1). Bei einem balancierten Baum sind das O(log n); bei einem Baum, der wie ein einzelner Pfad geformt ist, sind es O(n).

Wie unterscheidet sich der LCA in einem binären Suchbaum vom LCA in einem Binärbaum?

In einem gewöhnlichen Binärbaum kann sich ein Wert überall befinden, daher durchsuchst du beide Teilbäume jedes Knotens, und der Aufwand beträgt O(n). In einem Suchbaum verrät dir der Vergleich der beiden Werte mit einem Knoten, auf welcher Seite sich jeder von ihnen befindet, sodass du einem einzigen Pfad von der Wurzel aus folgst. Die rekursive Methode für beliebige Bäume funktioniert zwar auch bei einem Suchbaum, aber dabei geht diese Information verloren.

Kann ein Knoten sein eigener tiefster gemeinsamer Vorfahr sein?

Ja. Ein Knoten gilt als Vorfahr seiner selbst. Wenn also p über q liegt, lautet die Antwort p. Dieselbe Regel ergibt p, wenn die beiden Werte gleich sind. Der Durchlauf behandelt beide Fälle: Er endet, sobald der aktuelle Knoten einem der Werte entspricht.

Warum endet der Weg am ersten Knoten, an dem sich p und q trennen?

An diesem Knoten ist ein Wert kleiner und der andere größer, also befinden sie sich in verschiedenen Teilbäumen. Jeder darunterliegende Knoten liegt nur in einem dieser Teilbäume und kann daher nicht beide enthalten. Der Verzweigungsknoten enthält beide, und kein tiefer liegender Knoten tut das – genau das ist die Definition des tiefsten gemeinsamen Vorfahren.

Python

def lowestCommonAncestor(tree, p, q):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

tree = [20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15]
p = 3
q = 15

Erwartet

Lowest Common Ancestor of a BST

Funktion

Einschränkungen

Beispiele

Tipps

Lösung

Den gesamten Baum durchsuchen und die Reihenfolge ignorieren

Vergleiche die beiden Suchpfade

Gehe nach unten, bis sich die Werte aufteilen

Stolperfallen und Grenzfälle

Häufige Fragen4

Ähnliche Aufgaben