Maximum Depth of Binary Tree
Du erhältst einen Binärbaum, der im Level-Order-Verfahren im Array tree gespeichert ist. 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 einen leeren Platz, und das Array kann mit zusätzlichen -1-Einträgen enden. Gib die maximale Tiefe des Baums zurück: die Anzahl der Knoten auf dem längsten Pfad von der Wurzel hinunter zu einem Blatt.
Funktion
- treeinteger-array
- der Binärbaum in Ebenenreihenfolge, wobei -1 für einen leeren Platz steht
- Gibt zurückinteger
- die Anzahl der Knoten auf dem längsten Pfad von der Wurzel zu einem Blatt
Einschränkungen
1 ≤ tree.length ≤ 32767- Jedes
tree[i]ist-1oder ein Wert mit0 ≤ tree[i] ≤ 1000. tree[0]ist niemals-1, daher hat der Baum mindestens einen Knoten.- Das Array kann nach dem letzten Knoten zusätzliche
-1-Einträge enthalten. - Beide Kinder einer leeren Stelle sind ebenfalls leer, und die Tiefe beträgt höchstens
14.
Beispiele
- Eingabe
- tree = [5, 8, 1, -1, 3, -1, -1, -1, -1, 6]
- Ausgabe
- 4
- Erklärung
- Der längste Pfad ist
5,8,3,6(Indizes0,1,4,9); er umfasst 4 Knoten. Der Pfad über1endet nach 2 Knoten.
- Eingabe
- tree = [7, -1, -1]
- Ausgabe
- 1
- Erklärung
- Die beiden
-1-Einträge sind die leeren Kindpositionen der Wurzel. Die Wurzel allein ist ein Pfad aus einem Knoten, daher beträgt die Tiefe1, nicht0.
- Eingabe
- tree = [2, -1, 9, -1, -1, -1, 4]
- Ausgabe
- 3
- Erklärung
- Die Wurzel
2hat kein linkes Kind. Ihr rechtes Kind9an Index2hat4an Index6als rechtes Kind, ein Pfad aus 3 Knoten.
Weiterführende Frage
Wie würdest du die Werte eines längsten Pfads von der Wurzel zu einem Blatt sowie dessen Länge zurückgeben? Wenn mehrere Pfade gleich lang sind, welchen würdest du zurückgeben?
Tipps
Öffne sie nacheinander. Jeder verrät ein bisschen mehr.
Denke an die Wurzel. Wenn du die Tiefe ihres linken Teilbaums und die Tiefe ihres rechten Teilbaums kennen würdest, wie groß wäre dann die Tiefe des gesamten Baums?
Es ist
1plus die größere der beiden Tiefen der Teilbäume für die Wurzel, und eine leere Stelle hat die Tiefe0. Dieselbe Regel gilt für jeden Knoten. Eine Traversierung, die die Tiefe jedes Knotens kennt, kann also die Antwort finden.Lege einen Stapel von Paaren an, bestehend aus einem Knotenindex und seiner Tiefe, wobei die Wurzel mit Tiefe 1 beginnt. Entferne ein Paar vom Stapel, merke dir die größte bisher gesehene Tiefe und füge jedes Kind bei
2*i+1und2*i+2zum Stapel hinzu, das innerhalb des Arrays liegt und nicht-1ist, und zwar mit einer um eins erhöhten Tiefe.
Lösung
Die Tiefe wird durch den längsten Zweig bestimmt, und du kannst nicht wissen, welcher Zweig das ist, ohne jeden Knoten zu besuchen. Deshalb brauchst du einen vollständigen Durchlauf, bei dem du für jeden Knoten weißt, wie tief er liegt. Rekursion, eine Breitensuche nach Ebenen und eine Tiefensuche mit einem eigenen Stack erledigen das jeweils in einem Durchlauf.
Rekursion auf den beiden Teilbäumen
Idee
Ein Kindknoten ist vorhanden, wenn sein Index innerhalb des Arrays liegt und sein Wert nicht -1 ist. Der tiefste Pfad durch einen Knoten führt in seinen tieferen Teilbaum hinab, daher ist die Tiefe am Index i gleich 1 für den Knoten plus dem größeren der Tiefen bei 2*i+1 und 2*i+2. Ein leerer Platz hat die Tiefe 0, wodurch die Rekursion endet. Ein Blatt erhält 1 + max(0, 0) = 1, und die Werte steigen bis zur Wurzel wieder an.
Jeder Knoten wird einmal besucht. Der Aufrufstapel enthält einen Frame pro Ebene des aktuellen Pfads, O(h), hier höchstens 14.
Algorithmus
- Schreibe
depth(i): Wennihinter dem Ende des Arrays liegt odertree[i]-1ist, gib0zurück. - Andernfalls gib
1 + max(depth(2*i+1), depth(2*i+2))zurück. - Gib
depth(0)zurück.
def maxDepth(tree):
def depth(i):
# An index past the end or a -1 is an empty spot: depth 0.
if i >= len(tree) or tree[i] == -1:
return 0
return 1 + max(depth(2 * i + 1), depth(2 * i + 2))
return depth(0)Breitensuche, Ebene für Ebene
Idee
Die maximale Tiefe ist die Anzahl der Ebenen, daher kannst du die Ebenen zählen, statt den Pfaden zu folgen. Eine Warteschlange besucht die Knoten der Reihe nach nach Ebenen. Lies vor jedem Durchlauf die Größe der Warteschlange ab: Diese Knoten gehören genau zu einer Ebene, denn die Kinder, die du während des Durchlaufs hinzufügst, werden hinter ihnen eingereiht. Jeder Durchlauf erhöht die Tiefe um 1. Im ersten Beispiel lauten die Durchläufe [5], [8, 1], [3] und [6], daher ist die Antwort 4.
Die Warteschlange enthält jeweils eine Ebene, also O(w) für die breiteste Ebene. Bei einem vollständigen Baum mit Tiefe 14 sind das 8192 der 16383 Knoten.
Algorithmus
- Lege den Wurzelindex
0in eine Warteschlange und setzedepth = 0. - Solange die Warteschlange nicht leer ist, addiere
1zudepthund lies die Größe der Warteschlange ab. - Nimm so viele Indizes heraus. Lege für jeden die Kindindizes
2*i+1und2*i+2in die Warteschlange, sofern sie innerhalb des Arrays liegen und nicht-1sind. - Wenn die Warteschlange leer ist, gib
depthzurück.
from collections import deque
def maxDepth(tree):
n = len(tree)
queue = deque([0])
depth = 0
while queue:
depth += 1
for _ in range(len(queue)): # exactly the nodes of this level
i = queue.popleft()
for child in (2 * i + 1, 2 * i + 2):
if child < n and tree[child] != -1:
queue.append(child)
return depthTiefensuche mit einem expliziten Stapel
Idee
Verwende einen eigenen Stapel mit Paaren aus einem Knotenindex und seiner Tiefe, da nichts anderes speichert, wie weit unten sich ein Knoten befindet. Beginne mit (0, 1), der Wurzel in Tiefe 1. Jeder Knoten wird einmal auf den Stapel gelegt und trägt dabei die Länge des Pfads, der zu ihm führt. Die größte Tiefe, die du vom Stapel nimmst, ist also die Antwort. Im ersten Beispiel wird die 6 als (9, 4) auf den Stapel gelegt.
Der Stapel enthält ungefähr ein ausstehendes Geschwister pro Ebene, O(h), und es gibt keinen Aufrufstapel, der überlaufen könnte. Derselbe Code funktioniert bei einem zeigerbasierten Baum beliebiger Tiefe.
Algorithmus
- Lege
(0, 1)auf einen Stapel und setzebest = 0. - Nimm ein Paar
(i, depth)vom Stapel und setzebestauf den größeren Wert vonbestunddepth. - Für jeden Kindindex
2*i+1und2*i+2, der sich innerhalb des Arrays befindet und nicht-1ist, lege ihn zusammen mitdepth + 1auf den Stapel. - Wiederhole dies, bis der Stapel leer ist, und gib dann
bestzurück.
def maxDepth(tree):
n = len(tree)
best = 0
stack = [(0, 1)] # (node index, depth of that node); the root is never empty
while stack:
i, depth = stack.pop()
best = max(best, depth)
for child in (2 * i + 1, 2 * i + 2):
if child < n and tree[child] != -1:
stack.append((child, depth + 1))
return best
Stolperfallen und Grenzfälle
- Kanten statt Knoten zählen.
[7, -1, -1]hat die Tiefe1, nicht0. - Die Bereichsprüfung überspringen. Im ersten Beispiel hat die
6am Index 9 die Kindindizes 19 und 20, die außerhalb des Arrays liegen. Prüfechild < n, bevor dutree[child]liest. - Die Tiefe anhand der Länge des Arrays berechnen. Nachgestellte
-1-Einträge reichen bis zu einer Ebene ohne Knoten:[7, -1, -1]hat die Länge 3, aber die Tiefe 1. - Die Größe der Warteschlange innerhalb der Stapelschleife lesen. Während des Stapels hinzugefügte Kinder ändern sie, also speichere sie zuerst.
- Den Offset in Lua und R verwechseln, wo Arrays bei 1 beginnen. Behalte die Knotenindizes für
2*i+1bei 0 beginnend und liestree[i + 1].
Häufige Fragen3
Wie hoch ist die Zeitkomplexität der maximalen Tiefe eines Binärbaums?
Jeder Ansatz besucht jeden Knoten einmal, daher beträgt die Laufzeit O(n). Die Tiefensuche-Varianten benötigen O(h) zusätzlichen Speicherplatz für den aktuellen Pfad, wobei h die Tiefe ist. Die Breitensuche-Variante benötigt O(w) für die breiteste Ebene, also etwa die Hälfte der Knoten in einem vollständigen Baum.
Solltest du DFS oder BFS für die maximale Tiefe eines Binärbaums verwenden?
Beide laufen in O(n)-Zeit. Die Tiefensuche ist kürzer zu schreiben und benötigt Speicher proportional zur Tiefe, wodurch sie sich für breite, flache Bäume eignet. Die Breitensuche zählt die Ebenen direkt und benötigt Speicher proportional zur breitesten Ebene, wodurch sie sich für tiefe, schmale Bäume eignet. Bei der minimalen Tiefe ist BFS im Vorteil, da sie beim ersten Blatt abbrechen kann.
Was ist der Unterschied zwischen der Tiefe und der Höhe eines Binärbaums?
Die Tiefe eines Knotens zählt die Schritte von der Wurzel zu ihm hinunter; die Höhe zählt die Schritte von ihm hinunter bis zu seinem tiefsten Blatt. Die maximale Tiefe des Baums entspricht der Höhe der Wurzel. Bei diesem Problem werden Knoten gezählt, daher hat ein einzelner Knoten die Tiefe 1; zählt man Kanten, ist es eins weniger.
Ähnliche Aufgaben
Aufgaben mit denselben Ideen. Wer zwei oder drei davon löst, behält das Muster.
def maxDepth(tree):
# Schreibe hier den CodeTest #1
Test #2
Test #3
Argument
tree = [5, 8, 1, -1, 3, -1, -1, -1, -1, 6]
Erwartete Ausgabe
4