TreeNode-Klasse und BFS nach Ebenen
Erstellen Sie Binärbäume aus Arrays, implementieren Sie BFS mit einer Deque zur Ausgabe nach Ebenen und lösen Sie maximum-depth mit BFS.
TreeNode-Klasse und BFS nach Ebenen ist eine kostenlose DSA Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 1 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des DSA Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der DSA Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Die Grundlage der TreeNode-Klasse
Ein Binärbaum ist eine hierarchische Datenstruktur, bei der jeder Knoten höchstens zwei Kinder hat, die links und rechts genannt werden. In Python wird ein Knoten mit einer einfachen Klasse modelliert: class TreeNode: def __init__(self, val=0, left=None, right=None). Jedes Baumproblem in Interviews beginnt mit dieser Definition – Sie werden sie im Boilerplate-Code fast jedes LeetCode-Baumproblems sehen.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# Build a small tree manually:
# 1
# / \
# 2 3
# / \
# 4 5
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(root.val, root.left.val, root.right.val)Bäume aus Arrays erstellen
In Interviewaufgaben wird ein Baum häufig als Level-Order-Array vorgegeben, wobei None fehlende Knoten kennzeichnet. Für den Index i befindet sich das linke Kind an der Position 2i+1 und das rechte Kind an der Position 2i+2. Eine Hilfsfunktion zu schreiben, die dieses Array in miteinander verknüpfte TreeNodes deserialisiert, ist eine wertvolle Technik, die während Übungseinheiten Zeit spart.
from collections import deque
def build_tree(arr):
if not arr or arr[0] is None:
return None
root = TreeNode(arr[0])
q = deque([root])
i = 1
while q and i < len(arr):
node = q.popleft()
if i < len(arr) and arr[i] is not None:
node.left = TreeNode(arr[i])
q.append(node.left)
i += 1
if i < len(arr) and arr[i] is not None:
node.right = TreeNode(arr[i])
q.append(node.right)
i += 1
return root
root = build_tree([1, 2, 3, 4, 5, None, 6])
print(root.val, root.left.val, root.right.val)Was ist BFS und warum eine Queue?
Breitensuche (BFS) besucht alle Knoten in der Tiefe d, bevor sie einen Knoten in der Tiefe d+1 besucht. Diese Traversierung Ebene für Ebene entspricht genau dem Verhalten einer Queue (FIFO): Sie fügen die Wurzel in die Queue ein, verarbeiten die Knoten nacheinander und fügen dabei die Kinder jedes Knotens hinzu. Pythons collections.deque bietet O(1)-Operationen für appendleft und popleft und ist daher die richtige Wahl gegenüber einer einfachen Liste.
from collections import deque
def bfs_print(root):
if not root:
return
q = deque([root])
while q:
node = q.popleft()
print(node.val, end=' ')
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
bfs_print(root) # 1 2 3 4Level-Order-BFS: Gruppierung nach Ebenen
Die standardmäßige BFS-Variante gruppiert Knoten nach Ebenen, indem sie die Queue-Größe zu Beginn jeder Iteration erfasst. Verarbeiten Sie genau so viele Knoten, sammeln Sie ihre Werte und wechseln Sie anschließend zur nächsten Ebene. Das ergibt eine Liste von Listen – ein sehr häufiges Ausgabeformat in Interviews für Probleme wie die Level-Order-Traversierung eines Binärbaums, die Zickzack-Traversierung und die Ansicht von rechts.
from collections import deque
def level_order(root):
if not root:
return []
result = []
q = deque([root])
while q:
level_size = len(q)
level = []
for _ in range(level_size):
node = q.popleft()
level.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
result.append(level)
return result
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
print(level_order(root)) # [[1], [2, 3], [4]]Maximale Tiefe mit BFS
Die maximale Tiefe eines Binärbaums entspricht der Anzahl der Ebenen in seiner BFS-Traversierung. Zählen Sie einfach, wie oft Sie eine Ebenenschleife abschließen. Damit erhalten Sie eine Lösung mit O(n) Laufzeit und O(w) Speicherplatz, wobei w die maximale Breite des Baums ist. Bei einem balancierten Baum ist w O(n/2), daher beträgt der Speicherbedarf im Worst Case O(n).
from collections import deque
def max_depth_bfs(root):
if not root:
return 0
depth = 0
q = deque([root])
while q:
depth += 1
for _ in range(len(q)):
node = q.popleft()
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return depth
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
print(max_depth_bfs(root)) # 3Ansicht eines Binärbaums von rechts
Die Ansicht von rechts gibt den letzten sichtbaren Knoten zurück, wenn Sie den Baum von rechts betrachten – also das letzte Element jeder Ebene der BFS-Traversierung. Dies ist eine direkte Anwendung der Level-Order-BFS: Erfassen Sie den letzten Knoten in jeder Ebenenschleife. Die Zeitkomplexität beträgt O(n), der Speicherbedarf für die Queue O(w).
from collections import deque
def right_side_view(root):
if not root:
return []
result = []
q = deque([root])
while q:
level_size = len(q)
for i in range(level_size):
node = q.popleft()
if i == level_size - 1:
result.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return result
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.right = TreeNode(5)
print(right_side_view(root)) # [1, 3, 5]Zickzack-Level-Order-Durchlauf
Beim Zickzack-Durchlauf werden Knoten auf ungeraden Ebenen von links nach rechts und auf geraden Ebenen von rechts nach links gesammelt. Die sauberste Implementierung lässt die BFS-Warteschlange unverändert und kehrt einfach die Listen abwechselnder Ebenen um, bevor sie an das Ergebnis angehängt werden. Verfolgen Sie die Richtung mit einem booleschen Flag, das auf jeder Ebene wechselt. Dadurch vermeiden Sie die Komplexität einer Deque mit zwei Enden in der inneren Schleife.
from collections import deque
def zigzag_level_order(root):
if not root:
return []
result = []
q = deque([root])
left_to_right = True
while q:
level = []
for _ in range(len(q)):
node = q.popleft()
level.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
result.append(level if left_to_right else level[::-1])
left_to_right = not left_to_right
return result
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
print(zigzag_level_order(root))Analyse der Speicherkomplexität von BFS
BFS benötigt O(w) Speicher, wobei w die maximale Breite des Baums ist. Bei einem perfekten Binärbaum mit n Knoten enthält die letzte Ebene (n+1)/2 Knoten – daher kann BFS gleichzeitig bis zu n/2 Knoten in der Warteschlange halten. Damit benötigt BFS bei breiten, ausgeglichenen Bäumen mehr Speicher als DFS (O(h)), ist bei tiefen, schiefen Bäumen jedoch speichereffizienter, da die Tiefe des DFS-Aufrufstapels n entspricht.
# Space comparison: BFS vs DFS on a complete binary tree
# n=15 nodes, height=4
# BFS max queue size = 8 (last level)
# DFS max call stack = 4 (height)
# For a skewed tree (like a linked list):
# n=1000 nodes
# BFS max queue size = 1 (always 1 node per level)
# DFS max call stack = 1000 (recursion depth -> stack overflow!)
from collections import deque
def skewed_tree(n):
root = TreeNode(1)
cur = root
for i in range(2, n+1):
cur.right = TreeNode(i)
cur = cur.right
return root
root = skewed_tree(10)
print('BFS on skewed tree is safe')Durchschnitt der Ebenen eines Binärbaums
Das Berechnen des Durchschnittswerts jeder Ebene ist eine weitere direkte Anwendung von BFS. Addieren Sie alle Werte einer Ebene, teilen Sie die Summe durch die Anzahl der Werte und hängen Sie das Ergebnis an die Ergebnisliste an. Bei dieser Aufgabe wird geprüft, ob Sie innerhalb der Ebenenschleife Berechnungen durchführen können. Verwenden Sie in Python 3 immer eine float-Division (den Operator /) und behandeln Sie den Sonderfall eines leeren Baums gleich am Anfang.
from collections import deque
def average_of_levels(root):
if not root:
return []
result = []
q = deque([root])
while q:
size = len(q)
total = 0
for _ in range(size):
node = q.popleft()
total += node.val
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
result.append(total / size)
return result
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
print(average_of_levels(root)) # [3.0, 14.5, 11.0]Minimale Tiefe mit BFS
Die minimale Tiefe ist die Entfernung von der Wurzel zum nächstgelegenen Blatt (einem Knoten ohne Kindknoten). BFS findet diese optimal: Der erste Blattknoten, der während des Level-Order-Durchlaufs gefunden wird, liegt garantiert auf der minimalen Tiefe. Geben Sie die aktuelle Tiefe zurück, sobald Sie ein Blatt erreichen. Im schlimmsten Fall beträgt die Laufzeit O(n), bei ausgeglichenen Bäumen wird die Suche jedoch häufig deutlich früher beendet.
from collections import deque
def min_depth(root):
if not root:
return 0
q = deque([(root, 1)])
while q:
node, depth = q.popleft()
# A leaf has no children
if not node.left and not node.right:
return depth
if node.left:
q.append((node.left, depth + 1))
if node.right:
q.append((node.right, depth + 1))
return 0
root = TreeNode(2)
root.left = TreeNode(3)
root.left.left = TreeNode(4)
root.right = TreeNode(5) # leaf at depth 2
print(min_depth(root)) # 2Verknüpfen von Geschwistern auf derselben Ebene
Beim Problem der next-right-Zeiger sollen Sie jeden Knoten mit seinem rechten Nachbarn auf derselben Ebene verknüpfen. Mit BFS ist das unkompliziert: Setzen Sie innerhalb der Schleife für jede Ebene bei allen Knoten außer dem letzten node.next = q[0]. Dies ist ein klassisches Beispiel dafür, dass BFS die Lösung offensichtlich macht, während DFS eine sorgfältige Zeigerverfolgung über verschiedene Teilbäume hinweg erfordert.
from collections import deque
class Node:
def __init__(self, val=0, left=None, right=None, next=None):
self.val = val
self.left = left
self.right = right
self.next = next
def connect(root):
if not root:
return root
q = deque([root])
while q:
size = len(q)
for i in range(size):
node = q.popleft()
if i < size - 1:
node.next = q[0]
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return root
print('BFS connect: O(n) time, O(w) space')Kurzer Test
Testen Sie Ihr Verständnis der Konzepte aus Data Structures & Algorithms — Coding Interview Prep in dieser Lektion.
Zusammenfassung der Lektion
In dieser Lektion haben Sie Folgendes gelernt: die Definition der TreeNode-Klasse und das Erstellen von Bäumen aus Arrays, die Level-Order-BFS mit einer Deque unter Verwendung des Tricks mit der Ebenengröße zum Gruppieren von Knoten sowie Anwendungen wie maximale Tiefe, minimale Tiefe, Ansicht von der rechten Seite, Zickzack-Durchlauf und Durchschnittswerte der Ebenen. Als Nächstes untersuchen wir rekursive DFS-Durchlaufreihenfolgen.
Häufig gestellte Fragen
Ist die Lektion „TreeNode-Klasse und BFS nach Ebenen“ kostenlos?
Ja — der vollständige Text von „TreeNode-Klasse und BFS nach Ebenen“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des DSA Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der DSA Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „TreeNode-Klasse und BFS nach Ebenen“?
Erstellen Sie Binärbäume aus Arrays, implementieren Sie BFS mit einer Deque zur Ausgabe nach Ebenen und lösen Sie maximum-depth mit BFS. Du übst DSA Interview Prep mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um DSA Interview Prep zu starten?
Keine Vorkenntnisse erforderlich. DSA Interview Prep auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 1 von 4.
Wie lange dauert die Lektion „TreeNode-Klasse und BFS nach Ebenen“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser DSA Interview Prep-Lektion Code schreiben und ausführen?
Ja. Jede DSA Interview Prep-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- TreeNode-Klasse und BFS nach Ebenen
- In-Order-, Pre-Order- und Post-Order-DFS
- Durchmesser, Höhe und balancierte Bäume
- Pfadsumme und niedrigster gemeinsamer Vorfahr