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 eine leere Stelle, 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
- den Binärbaum in Ebenenreihenfolge, wobei -1 eine leere Stelle kennzeichnet
- 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, 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.
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) und enthält 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 Tiefe1und nicht0.
- Eingabe
- tree = [2, -1, 9, -1, -1, -1, 4]
- Ausgabe
- 3
- Erklärung
- Die Wurzel
2hat kein linkes Kind. Ihr rechtes Kind9am Index2hat die4am Index6als rechtes Kind, ein Pfad aus 3 Knoten.
+13 versteckte Tests beim Einreichen
Weiterführende Frage
Wie würdest du die Werte auf einem längsten Pfad von der Wurzel zu einem Blatt zurückgeben, nicht nur dessen Länge? Falls mehrere Pfade gleich lang sind, welchen würdest du zurückgeben, und wie würdest du das im Vertrag angeben?
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?
Sie ist
1für die Wurzel plus die größere der beiden Teilbaumtiefen, und eine leere Stelle hat die Tiefe0. Dieselbe Regel gilt an jedem Knoten, daher kann eine Traversierung, die weiß, wie tief jeder Knoten ist, die Antwort finden.Verwende einen Stapel mit Paaren aus einem Knotenindex und seiner Tiefe, beginnend mit der Wurzel in Tiefe 1. Entferne ein Paar vom Stapel, merke dir die größte bisher gesehene Tiefe und füge jedes Kind bei
2*i+1und2*i+2hinzu, das sich innerhalb des Arrays befindet und nicht-1ist, und zwar mit der um eins erhöhten Tiefe.
Lösung
Die Tiefe wird durch den längsten einzelnen Zweig bestimmt, und du kannst nicht feststellen, welcher Zweig das ist, ohne jeden Knoten anzusehen. Die Aufgabe besteht also in einer vollständigen Traversierung, bei der die Tiefe an jedem Knoten bekannt ist. Rekursion, eine Breitensuche Ebene für Ebene und eine Tiefensuche mit einem eigenen Stack erledigen das in einem Durchlauf; sie unterscheiden sich darin, wie sie nachverfolgen, wo sie sich befinden.
Rekursion auf den beiden Teilbäumen
Idee
Zuerst geht es darum, sich im Array zu bewegen. 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 ist nur dann vorhanden, wenn sein Index innerhalb des Arrays liegt und der Wert dort nicht -1 ist. In [5, 8, 1, -1, 3, -1, -1, -1, -1, 6] hat die Wurzel 5 Kinder an den Indizes 1 und 2, der Knoten 8 am Index 1 hat an Position 3 einen leeren Platz links und rechts davon den Knoten 3 am Index 4, und dieser Knoten 3 hat darunter den Knoten 6 am Index 9.
Nun zur Idee. Der tiefste Pfad durch einen Knoten führt in den tieferen seiner beiden Teilbäume. Die Tiefe des Teilbaums am Index i ist also 1 für den Knoten selbst plus dem größeren der Tiefen an den Indizes 2*i+1 und 2*i+2. Ein leerer Platz hat die Tiefe 0; damit endet die Rekursion. Ein Blatt erhält 1 + max(0, 0) = 1, und die Werte steigen bis zur Wurzel zurück an.
Jeder Knoten wird einmal besucht, daher beträgt der Zeitaufwand O(n). Der Aufrufstapel enthält einen Frame pro Ebene des aktuellen Pfads, also O(h), wobei h die Tiefe ist und hier höchstens 14 beträgt. Diese Begrenzung macht die Rekursion in diesem Problem sicher. Bei einem zeigerbasierten Baum, der wie eine lange Kette geformt ist, würde derselbe Code das Rekursionslimit erreichen, das in Python bei 1000 Frames liegt.
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 im Baum. Du kannst also die Ebenen zählen, statt den Pfaden zu folgen. Eine Warteschlange besucht die Knoten in Ebenenreihenfolge: Beginne mit der Wurzel, und füge jedes Mal, wenn du einen Knoten herausnimmst, seine tatsächlichen Kinder hinten an.
Um die Ebenen zu zählen, verarbeitest du die Warteschlange stapelweise. Lies vor jedem Stapel ab, wie viele Knoten sich in der Warteschlange befinden. Das sind genau die Knoten einer Ebene, denn die Kinder, die du während des Stapels hinzufügst, kommen hinter ihnen zu liegen. Nimm so viele Knoten heraus, füge ihre Kinder in die Warteschlange ein und addiere 1 zur Tiefe. Wenn die Warteschlange leer ist, entspricht die Tiefe der Anzahl der Stapel. Im ersten Beispiel sind die Stapel [5], [8, 1], [3] und [6], also lautet die Antwort 4.
Jeder Knoten wird einmal in die Warteschlange eingefügt und einmal daraus entfernt: Zeitaufwand O(n). Die Warteschlange enthält jeweils eine Ebene; der Speicherbedarf beträgt O(w) für die breiteste Ebene w. Bei einem vollständigen Baum enthält die unterste Ebene etwa die Hälfte der Knoten: 8192 von 16383 bei Tiefe 14.
Algorithmus
- Füge den Wurzelindex
0in eine Warteschlange ein und setzedepth = 0. - Solange die Warteschlange nicht leer ist, addiere
1zudepthund lies die Größe der Warteschlange aus. - Nimm so viele Indizes heraus. Füge für jeden die untergeordneten Indizes
2*i+1und2*i+2in die Warteschlange ein, die sich innerhalb des Arrays befinden 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
Du kannst Pfaden folgen, wie es die Rekursion tut, ohne einen einzigen rekursiven Aufruf zu machen. Verwalte deinen eigenen Stack und speichere jeden Knoten zusammen mit seiner Tiefe, da sich sonst nichts merkt, wie weit unten er sich befindet. Beginne mit dem Paar (0, 1): der Wurzel auf Tiefe 1.
Nimm ein Paar vom Stack, vergleiche seine Tiefe mit der bisher größten und füge jedes vorhandene Kind mit depth + 1 hinzu. Jeder Knoten im Baum wird genau einmal hinzugefügt und trägt dabei die Länge des Pfads, der zu ihm führt. Daher ist die größte Tiefe, die du entnimmst, die Antwort. Im ersten Beispiel wird die 6 am Index 9 als (9, 4) hinzugefügt, und kein Paar geht tiefer.
Die Laufzeit beträgt O(n). Der Stack enthält die noch ausstehenden Geschwister entlang des aktuellen Pfads, höchstens ungefähr eines pro Ebene. Daher beträgt der Speicherbedarf O(h), genauso wie bei der Rekursion, aber ohne Aufrufstack, der überlaufen könnte. Auf diese Variante solltest du zurückgreifen, wenn ein Baum tief sein kann; sie lässt sich unverändert auf zeigerbasierte Bäume übertragen.
Algorithmus
- Lege
(0, 1)auf einen Stapel und setzebest = 0. - Entnimm das Paar
(i, depth)und setzebestauf den größeren Wert vonbestunddepth. - Lege für jeden Kindindex
2*i+1und2*i+2, der sich innerhalb des Arrays befindet und nicht-1ist, diesen 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
Die meisten falschen Antworten bei diesem Problem liegen um eins daneben oder entstehen dadurch, dass eine leere Stelle als Knoten behandelt wird.
- Kanten statt Knoten zählen. Ein einzelner Knoten hat hier die Tiefe
1; für ihn0oder für einen Pfad mit 4 Knoten3zurückzugeben, ist jeweils um eins zu wenig. - Die Bereichsprüfung überspringen. 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
child < n, bevor dutree[child]liest. - Die Tiefe anhand der Arraylänge ablesen. Am Ende kann das Array zusätzliche
-1-Einträge enthalten, sodass seine Länge zu einer tieferen Ebene gehören kann als jeder echte Knoten. -1als Wert behandeln. Es kennzeichnet einen fehlenden Knoten und darf daher weder auf den Stapel gelegt noch in die Warteschlange eingefügt oder gezählt werden.- Annehmen, dass der Baum ausgeglichen ist. Die Antwort ergibt sich aus dem längsten Zweig, wie bei einer Kette aus 14 Knoten nach links, bei der jede rechte Stelle leer ist.
- In der Breitensuche-Version die Größe der Warteschlange innerhalb der Schleife abfragen. Die Größe ändert sich, sobald Kinder hinzugefügt werden, also speichere sie, bevor der Durchlauf beginnt.
- Den Versatz in Lua und R verwechseln, wo Arrays bei 1 beginnen. Behalte für die Rechnung mit
2*i+1die 0-basierten Knotenindizes bei und liestree[i + 1].
Häufige Fragen4
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 gerade erkundeten Pfad, wobei h die Tiefe ist. Die Breitensuche-Variante benötigt O(w) für die breiteste Ebene, die bei einem vollständigen Baum etwa die Hälfte der Knoten enthalten kann.
Solltest du für die maximale Tiefe eines binären Baums DFS oder BFS verwenden?
Beide liefern in O(n)-Zeit die richtige Antwort. Die Tiefensuche ist kürzer zu schreiben und benötigt Speicher proportional zur Tiefe, weshalb sie sich für breite, flache Bäume eignet. Die Breitensuche zählt die Ebenen direkt und benötigt Speicher proportional zur breitesten Ebene, weshalb sie sich für tiefe, schmale Bäume eignet. Bei der minimalen Tiefe hat die Breitensuche einen Vorteil, da sie beim ersten Blattknoten, auf den sie trifft, abbrechen kann.
Wie findest du die maximale Tiefe eines Binärbaums ohne Rekursion?
Verwende einen expliziten Stack aus Paaren: einem Knoten und seiner Tiefe. Beginne mit der Wurzel in Tiefe 1, nimm ein Paar vom Stack, erfasse seine Tiefe und lege jedes Kind mit der um eins erhöhten Tiefe auf den Stack. Die größte Tiefe, die du entnimmst, ist die Antwort. Eine Warteschlange, die Ebene für Ebene verarbeitet wird, funktioniert ebenfalls; zähle dabei pro Ebene eins.
Was ist der Unterschied zwischen der Tiefe und der Höhe eines binären Baums?
Die Tiefe eines Knotens zählt die Schritte von der Wurzel bis zu ihm, und die Höhe eines Knotens zählt die Schritte von ihm bis zu seinem tiefsten Blatt. Die maximale Tiefe des Baums und die Höhe der Wurzel sind dieselbe Zahl. Bei diesem Problem werden Knoten gezählt, daher hat ein einzelner Knoten die Tiefe 1; manche Bücher zählen stattdessen Kanten, wodurch sich ein Wert ergibt, der um eins kleiner ist.
Ähnliche Aufgaben
Aufgaben mit denselben Ideen. Wer zwei oder drei davon löst, behält das Muster.
Python
def maxDepth(tree):
# Schreibe hier den CodeFall 1
Fall 2
Fall 3
Eingabe
tree = [5, 8, 1, -1, 3, -1, -1, -1, -1, 6]
Erwartet
4