Lowest Common Ancestor of a BST
Du erhältst einen binären Suchbaum, der in Heap-Reihenfolge im Array tree gespeichert ist: Die Wurzel steht am Index 0, die Kinder des Index i stehen bei 2*i+1 (links) und 2*i+2 (rechts), und -1 kennzeichnet eine leere Stelle. Jeder Wert im linken Teilbaum eines Knotens ist kleiner als der Wert des Knotens, und jeder Wert in seinem rechten Teilbaum ist größer.
Schreibe lowestCommonAncestor, das den Wert des niedrigsten gemeinsamen Vorfahren der Werte p und q zurückgibt, die beide im Baum vorkommen: den tiefsten Knoten, der beide in seinem Teilbaum hat. Ein Knoten ist Teil seines eigenen Teilbaums. Wenn also p über q liegt, lautet die Antwort p.
Funktion
- treeinteger-array
- der binäre Suchbaum in Ebenenreihenfolge, mit -1 für eine leere Stelle
- pinteger
- der erste zu findende 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-1oder ein Wert mit0 ≤ tree[i] ≤ 105. tree[0]ist niemals-1, also 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.
pundqsind 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
- Wenn man von
3und15aus nach oben geht, ist der erste Knoten, den beide erreichen,8:3ist sein linkes Kind, und15hängt unter12auf seiner rechten Seite. Die Wurzel20ist 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
10ist das linke Kind von12, und ein Knoten zählt als sein eigener Vorfahr, also enthält12beide Werte und kein darunterliegender Knoten. Hier istpder größere Wert.
- Eingabe
- tree = [50, 30, 70, 20, 40, 60, 80, -1, -1, -1, -1, 55]p = 55q = 80
- Ausgabe
- 70
- Erklärung
- Beide Werte sind größer als die Wurzel
50, also liegen beide rechts davon. Bei70trennen sie sich:55ist kleiner und liegt links davon, unterhalb von60, und80ist größer.
Weiterführende Frage
Was würdest du ändern, wenn p oder q im Baum fehlen könnte und die Funktion in diesem Fall -1 zurückgeben müsste?
Tipps
Öffne sie nacheinander. Jeder verrät ein bisschen mehr.
Stehe an der Wurzel. Wenn sowohl
pals auchqkleiner als ihr Wert sind, in welchem Teilbaum befinden sich dann beide Knoten?Solange sich beide Werte auf derselben Seite des aktuellen Knotens befinden, liegt auch jeder gemeinsame Vorfahr weiter unten auf dieser Seite. Der erste Knoten, bei dem sie sich nicht auf derselben Seite befinden oder der einen der beiden Werte enthält, ist der gesuchte.
Beginne bei Index
0. Solange beide Werte kleiner alstree[i]sind, gehe zu2*i+1; solange beide größer sind, gehe zu2*i+2. Andernfalls gibtree[i]zurück.
Lösung
Ein Suchbaum zeigt dir an jedem Knoten, wo sich ein Wert befindet: kleinere Werte links, größere rechts. Beginne an der Wurzel und gehe in die Richtung, in der sich beide Werte befinden. Der erste Knoten, an dem sie nicht mehr auf derselben Seite liegen, ist die Antwort, und du erreichst ihn auf einem Pfad.
Den gesamten Baum durchsuchen und dabei die Reihenfolge ignorieren
Idee
Diese Methode funktioniert bei jedem Binärbaum. Ein rekursives find(i) gibt an, was der Teilbaum bei i enthält. Ein Knoten, der p oder q enthält, gibt sich selbst zurück: Liegt der andere Wert unter ihm, ist er die Antwort; wenn nicht, sieht ein weiter oben liegender Knoten beide. Jeder andere Knoten fragt beide Kinder ab. Wenn beide etwas zurückgeben, liegen p und q auf verschiedenen Seiten, und dieser Knoten ist der Punkt, an dem sie zusammentreffen; wenn nur einer etwas zurückgibt, wird dieses Ergebnis nach oben weitergegeben.
Bei 3 und 15 erhält die 8 von links den Index 3 und von rechts den Index 10 und gibt sich selbst zurück. Die Methode besucht möglicherweise jeden Knoten: Laufzeit O(n) und O(h) für die Rekursion.
Algorithmus
- Schreibe
find(i). Wenn die Stelle beiileer ist (hinter dem Ende oder-1), gib-1zurück. - Wenn
tree[i]poderqist, gibizurück. - Rufe
findfür2*i+1und2*i+2auf. Wenn beide etwas gefunden haben, gibizurü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
Suche wie üblich nach einem Wert: Beginne an der Wurzel, gehe nach links, wenn er kleiner als der Knoten ist, und nach rechts, wenn er größer ist. Der Pfad von der Wurzel zu einem Knoten ist eindeutig, daher durchläuft der Suchweg alle Vorfahren des Werts und nichts anderes.
Notiere beide Suchwege. Sie enthalten dieselben Knoten, bis die Werte unterschiedliche Wege einschlagen. Daher listet der gemeinsame Anfang die gemeinsamen Vorfahren auf, und sein letzter Wert ist der niedrigste. Für 3 und 15 lauten die Pfade 20, 8, 3 und 20, 8, 12, 15: Sie haben 20, 8 gemeinsam, also lautet die Antwort 8. Jeder Suchweg macht einen Schritt pro Ebene: Laufzeit O(h) und O(h) Speicherplatz für die Listen.
Algorithmus
- Schreibe
path(target): Beginne bei Index0, notieretree[i]und stoppe, wenn er gleichtargetist; andernfalls gehe zu2*i+1, wenntargetkleiner ist, und zu2*i+2, wenn er größer ist. - Erstelle den Pfad zu
pund den Pfad zuq. - Gehe beide Listen vom Anfang an durch und gib den letzten Wert zurück, den sie gemeinsam haben.
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 answerGehe so lange nach unten, bis sich die Werte aufteilen
Idee
Die beiden Pfade stimmen überein, solange p und q sich in dieselbe Richtung bewegen, also gehe beide gleichzeitig entlang. An einem Knoten mit dem Wert v: Sind beide Werte kleiner, liegen beide im linken Teilbaum, ebenso wie jeder gemeinsame Vorfahr unterhalb von v: Gehe nach links. Sind beide größer, gehe nach rechts.
Andernfalls ist ein Wert kleiner und der andere größer, sodass kein Kind von v beide enthält, oder einer der beiden Werte entspricht v, das sein eigener Vorfahr ist. In beiden Fällen ist v der tiefste Knoten oberhalb beider Werte. Im dritten Beispiel liegt 50 unterhalb beider Werte, also gehst du nach rechts zu 70, wo 55 kleiner und 80 größer ist. Ein Vergleichspaar pro Ebene ergibt eine Laufzeit von O(h) und einen Speicherbedarf von O(1).
Algorithmus
- Beginne bei Index
i = 0. - Lies
v = tree[i]. - Wenn
p < vundq < v, gehe zu2*i+1und wiederhole den Vorgang. - Wenn
p > vundq > v, gehe zu2*i+2und wiederhole den Vorgang. - Andernfalls gib
vzurü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
≤und≥in den Tests für die Schritte verwenden. Beip = 12undq = 10geht der Lauf an12vorbei bis zu10und gibt dann10zurück oder läuft über den Baum hinaus.- Annehmen, dass
p < q. Im zweiten Beispiel istpder größere Wert. Vergleiche beide Werte mit dem Knoten oder vertausche sie vorher. - Den Index statt des Werts zurückgeben. Die Antwort ist
tree[i], nichti. - In Lua und R beginnen Arrays bei 1. Behalte für die Rechnung
2*i+1die 0-basierten Knotenindizes bei und liestree[i + 1].
Häufige Fragen3
Wie hoch ist die Zeitkomplexität für den niedrigsten gemeinsamen Vorfahren in einem BST?
Der Weg von der Wurzel folgt einem Pfad, daher benötigt er bei einem Baum mit der Tiefe h O(h) Zeit und O(1) zusätzlichen Speicherplatz. Bei einem balancierten Baum sind das O(log n); bei einem Baum, der wie ein einzelner Pfad geformt ist, O(n).
Wie unterscheidet sich der LCA in einem binären Suchbaum vom LCA in einem binären Baum?
In einem gewöhnlichen Binärbaum kann ein Wert überall sein, daher musst du jeden Knoten durchsuchen: Aufwand O(n). In einem Suchbaum sagt dir der Vergleich der beiden Werte mit einem Knoten, auf welcher Seite sich die Werte befinden, sodass du einem Pfad von der Wurzel aus folgst.
Kann ein Knoten sein eigener niedrigster gemeinsamer Vorfahr sein?
Ja. Ein Knoten zählt als Vorfahr seiner selbst. Wenn also p über q steht, lautet die Antwort p, und wenn die beiden Werte gleich sind, ist die Antwort dieser Wert.
Ähnliche Aufgaben
Aufgaben mit denselben Ideen. Wer zwei oder drei davon löst, behält das Muster.
def lowestCommonAncestor(tree, p, q):
# Schreibe hier den CodeTest #1
Test #2
Test #3
Argumente
tree = [20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15] p = 3 q = 15
Erwartete Ausgabe
8