Lowest Common Ancestor of a Binary Tree

Q: Wie unterscheidet sich das vom niedrigsten gemeinsamen Vorfahren in einem binären Suchbaum?

In einem Suchbaum zeigt dir der Vergleich von p und q mit einem Knoten, auf welcher Seite sich die beiden befinden, sodass ein Pfad von der Wurzel die Antwort in O(h) findet. Hier sagt ein Vergleich nichts aus, also durchsuchst du die Teilbäume.

Q: Kannst du den niedrigsten gemeinsamen Vorfahren mithilfe von Elternzeigern finden?

Ja. In diesem Array ist der Elternknoten des Index i (i-1)/2 , abgerundet. Bewege den größeren der beiden Indizes zu seinem Elternknoten, bis sie gleich sind; ein größerer Index ist niemals ein Vorfahr eines kleineren. Bei verketteten Knoten speicherst du die Vorfahren von p in einer Menge und gehst von q aus nach oben bis zum ersten, der darin enthalten ist.

MittelBaumdurchlauf Rekursion

+10

Du erhältst einen Binärbaum im Array root in Heap-Anordnung: Die Wurzel befindet sich am Index 0, die Kinder des Index i an den Indizes 2*i+1 (links) und 2*i+2 (rechts), und -1 steht für eine leere Position. Die Werte sind verschieden und folgen keiner bestimmten Reihenfolge.

Gib den Wert des niedrigsten gemeinsamen Vorfahren von p und q zurück, den Werten zweier verschiedener Knoten: des tiefsten Knotens, dessen Teilbaum beide enthält. Ein Teilbaum schließt seinen obersten Knoten ein. Wenn also q unterhalb von p liegt, lautet die Antwort p.

Funktion

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

rootinteger-array: den Binärbaum in Level-Reihenfolge, mit -1 für eine leere Stelle
pinteger: der Wert eines Knotens
qinteger: der Wert eines anderen Knotens
Gibt zurückinteger: der Wert des niedrigsten Knotens, in dessen Teilbaum sich sowohl p als auch q befinden

Einschränkungen

2 ≤ root.length ≤ 32767
Jedes root[i] ist -1 oder ein Wert mit 0 ≤ root[i] ≤ 10⁴.
root[0] ist niemals -1, und der Baum hat mindestens zwei Knoten.
Das Array kann nach dem letzten Knoten mit zusätzlichen -1-Einträgen enden.
Beide Kinder eines leeren Feldes sind ebenfalls leer, und die Tiefe beträgt höchstens 14.
Alle Werte im Baum sind verschieden und folgen keiner Ordnung.
p und q sind die Werte zweier verschiedener Knoten im Baum, in beliebiger Reihenfolge.

Beispiele

Eingabe: root = [8, 3, 10, 6, 4, 12, 1, -1, -1, 7, 9]p = 6q = 9
Ausgabe: 3
Erklärung: 6 ist das linke Kind von 3, und 9 befindet sich unter 4 rechts von 3, also treffen sie sich bei 3. Ein Vergleich der Werte würde auf die Wurzel 8 verweisen: 6 ist kleiner und 9 größer.

Eingabe: root = [8, 3, 10, 6, 4, 12, 1, -1, -1, 7, 9]p = 4q = 7
Ausgabe: 4
Erklärung: 7 ist das linke Kind von 4, und der Teilbaum von 4 umfasst 4 selbst, also lautet die Antwort 4.

Eingabe: root = [1, -1, 6, -1, -1, 3, 0, -1, -1, -1, -1, -1, -1, -1, -1]p = 3q = 0
Ausgabe: 6
Erklärung: Die Wurzel 1 hat kein linkes Kind. Ihr rechtes Kind 6 hat links 3 und rechts 0, sodass die Werte bei 6 zusammentreffen.

Weiterführende Frage

Wenn p oder q fehlen können und -1 die Antwort ist: Welche Abkürzung in einem einzigen Durchlauf funktioniert dann nicht mehr, und wie kannst du trotzdem in einem Durchlauf fertig werden?

Tipps

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

0 von 3 geöffnet

Lösung

Keine Reihenfolge verrät dir, auf welcher Seite sich ein Wert befindet, also musst du nachsehen. Bei einem Durchlauf in Postorder kann jeder Teilbaum melden, was er gefunden hat, und die Werte treffen sich am ersten Knoten, der von beiden Seiten etwas erfährt.

Gehe nach unten und suche jede Seite ab

Idee

Gehe von der Wurzel aus nach unten und suche an jedem Knoten im linken Teilbaum nach p und q. Beide dort: gehe nach links. Keiner dort: gehe nach rechts. Jeweils einer: Die Werte teilen sich auf, und dieser Knoten ist die Antwort. Auch ein Knoten, der p oder q enthält, ist die Antwort, da der andere Wert darunter liegen muss. Für 6 und 9 findet die Wurzel beide in ihrem linken Teilbaum, und bei 3 enthält die einzelne 6 nur p.

Bei jedem Schritt nach unten wird ein ganzer Teilbaum durchsucht, daher kosten h Ebenen O(n·h) und bei einem hohen, schmalen Baum ohne Tiefenbegrenzung O(n²). Die Suche bei 8 hat bereits jeden Knoten unterhalb von 3 besucht, und beim Schritt bei 3 werden einige davon erneut besucht.

Algorithmus

Schreibe contains(i, value): false für eine leere Stelle (hinter dem Ende oder -1), true, wenn root[i] gleich value ist, andernfalls frage beide Kinder ab.
Beginne bei i = 0. Wenn root[i] p oder q ist, gib es zurück.
Wenn der linke Teilbaum bei 2*i+1 beide Werte enthält, gehe dorthin. Wenn er keinen der beiden Werte enthält, gehe zu 2*i+2.
Andernfalls gib root[i] zurück.

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

    def contains(i, value):
        # Is value somewhere in the subtree at index i?
        if i >= n or root[i] == -1:
            return False
        if root[i] == value:
            return True
        return contains(2 * i + 1, value) or contains(2 * i + 2, value)

    i = 0  # p and q are always inside the subtree at i
    while True:
        if root[i] == p or root[i] == q:
            return root[i]  # one value is here, the other is below it
        left = 2 * i + 1
        p_left = contains(left, p)
        q_left = contains(left, q)
        if p_left and q_left:
            i = left  # both on the left
        elif not p_left and not q_left:
            i = 2 * i + 2  # both on the right
        else:
            return root[i]  # one on each side

Ein Durchlauf in Postorder

Idee

Lass jeden Teilbaum einmal von unten nach oben antworten. find(i) gibt den Index des Antwortknotens zurück, wenn der Teilbaum bei i beide Werte enthält, den Index von p oder q, wenn er einen davon enthält, und -1, wenn er keinen von beiden enthält.

Ein Knoten, der p oder q enthält, gibt seinen eigenen Index zurück, ohne darunter nachzusehen. Befindet sich der andere Wert in seinem Teilbaum, ist dieser Knoten die Antwort; andernfalls erhält ein weiter oben liegender Knoten Rückmeldungen von beiden Seiten. Jeder andere Knoten fragt beide Kinder ab. Zwei Ergebnisse bedeuten, dass die Werte von verschiedenen Seiten nach oben gelangt sind und hier zusammentreffen. Ein einzelnes Ergebnis wird unverändert nach oben weitergegeben, egal ob es sich um einen der Werte oder die fertige Antwort handelt.

Im ersten Beispiel erhält 3 den Index 3 von links und 10 von rechts, gibt seinen eigenen Index 1 zurück, und die Wurzel gibt ihn weiter. Jeder Knoten wird einmal besucht: Zeit O(n), Rekursion O(h).

Algorithmus

find(i) gibt -1 für einen Index hinter dem Ende oder für ein -1 zurück.
Ein Knoten, dessen Wert p oder q ist, gibt i zurück, ohne darunter nachzusehen.
Jeder andere Knoten berechnet left = find(2*i+1) und right = find(2*i+2). Wenn keiner von beiden -1 ist, gibt er i zurück; andernfalls denjenigen, der nicht -1 ist, oder -1.
Gib root[find(0)] zurück.

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

    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 root[i] == -1:
            return -1
        if root[i] == p or root[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 root[find(0)]

Stolperfallen und Grenzfälle

Werte mit dem Knoten vergleichen. Der Baum ist nicht geordnet: Im ersten Beispiel endet diese Suche an der Wurzel 8 statt bei 3.
true oder false statt eines Index zurückgeben. Der übergeordnete Knoten kann nicht erkennen, ob die fertige Antwort bereits unter ihm liegt.
Ein Kind lesen, ohne die Länge zu überprüfen. Die 9 an Index 10 hat die Kindindizes 21 und 22, die hinter dem letzten Eintrag liegen.
find(0), also einen Index, statt root[find(0)] zurückgeben.
In Lua und R beginnen Arrays bei 1: Knotenindizes bei 0 belassen und root[i + 1] lesen.

Häufige Fragen3

Wie hoch ist die Zeitkomplexität für die Suche nach dem niedrigsten gemeinsamen Vorfahren in einem Binärbaum?

Der Postorder-Durchlauf besucht jeden Knoten höchstens einmal: O(n) Zeit. Der Rekursionsstack enthält einen Frame pro Ebene, daher beträgt der Speicherbedarf bei einem balancierten Baum O(log n) und bei einem pfadförmigen Baum O(n).

Wie unterscheidet sich das vom niedrigsten gemeinsamen Vorfahren in einem binären Suchbaum?

In einem Suchbaum zeigt dir der Vergleich von p und q mit einem Knoten, auf welcher Seite sich die beiden befinden, sodass ein Pfad von der Wurzel die Antwort in O(h) findet. Hier sagt ein Vergleich nichts aus, also durchsuchst du die Teilbäume.

Kannst du den niedrigsten gemeinsamen Vorfahren mithilfe von Elternzeigern finden?

Ja. In diesem Array ist der Elternknoten des Index i (i-1)/2, abgerundet. Bewege den größeren der beiden Indizes zu seinem Elternknoten, bis sie gleich sind; ein größerer Index ist niemals ein Vorfahr eines kleineren. Bei verketteten Knoten speicherst du die Vorfahren von p in einer Menge und gehst von q aus nach oben bis zum ersten, der darin enthalten ist.

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

Test #1

Test #2

Test #3

Argumente

root = [8, 3, 10, 6, 4, 12, 1, -1, -1, 7, 9]
p = 6
q = 9

Erwartete Ausgabe