Durchmesser, Höhe und balancierte Bäume
Berechnen Sie Durchmesser und Höhe eines Baums in einem einzigen DFS-Durchlauf mit einer Hilfsfunktion, die beide Werte zurückgibt, und prüfen Sie, ob der Baum höhenbalanciert ist.
Durchmesser, Höhe und balancierte Bäume ist eine kostenlose DSA Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 3 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.
Höhe eines Binärbaums
Die Höhe (oder maximale Tiefe) eines Binärbaums ist die Länge des längsten Pfads von der Wurzel zu einem beliebigen Blatt. Sie wird rekursiv berechnet: Die Höhe eines beliebigen Knotens ist 1 + max(height(left), height(right)), wobei für Nullknoten der Basisfall 0 gilt. Diese Postorder-Berechnung ist grundlegend – die Höhe bildet die Basis für Durchmesser, das Prüfen der Balance und AVL-Baum-Rotationen.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def height(root):
if not root:
return 0
return 1 + max(height(root.left), height(root.right))
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.left.left.left = TreeNode(6)
print(height(root)) # 4Durchmesser: der längste Pfad
Der Durchmesser eines Binärbaums ist die Länge des längsten Pfads zwischen zwei beliebigen Knoten (der Pfad muss nicht durch die Wurzel verlaufen). Die Pfadlänge wird in Kanten gemessen. Für jeden Knoten entspricht der durch ihn verlaufende Durchmesser height(left) + height(right). Der Gesamtdurchmesser ist der größte dieser Werte über alle Knoten des Baums hinweg.
def diameter_of_binary_tree(root):
max_diameter = [0] # use list to allow closure mutation
def dfs(node):
if not node:
return 0
left_h = dfs(node.left)
right_h = dfs(node.right)
# Diameter through this node
max_diameter[0] = max(max_diameter[0], left_h + right_h)
return 1 + max(left_h, right_h) # height for parent
dfs(root)
return max_diameter[0]
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(diameter_of_binary_tree(root)) # 3Ein einziger DFS-Durchlauf für den Durchmesser
Der naive Ansatz ruft height() bei jedem Knoten auf – bei einem ausgeglichenen Baum ergibt das O(n²). Die optimale Lösung berechnet die Höhe und aktualisiert den Durchmesser in einem einzigen DFS-Durchlauf. Die entscheidende Erkenntnis ist, dass die rekursive Funktion dfs() gleichzeitig zwei Aufgaben erfüllt: Sie gibt die Höhe für den Elternknoten zurück und aktualisiert als Seiteneffekt einen globalen maximalen Durchmesser. Dieses Postorder-Muster mit doppelter Funktion findet sich bei vielen Baumaufgaben.
# O(n^2) NAIVE: recomputes height for every node
def diameter_naive(root):
if not root:
return 0
through_root = height(root.left) + height(root.right)
in_left = diameter_naive(root.left)
in_right = diameter_naive(root.right)
return max(through_root, in_left, in_right)
# O(n) OPTIMAL: single DFS pass (shown in previous scene)
# The naive version is O(n^2) because height() is O(n)
# and it is called for every node.
print('Naive: O(n^2) | Optimal single-pass: O(n)')Prüfen, ob ein Binärbaum ausgeglichen ist
Ein Binärbaum ist höhenbalanciert, wenn sich die Höhen des linken und rechten Teilbaums jedes Knotens um höchstens eins unterscheiden. Der Brute-Force-Ansatz ruft height() bei jedem Knoten auf – O(n²). Der optimale Ansatz verwendet denselben Trick mit einem einzigen Durchlauf: Geben Sie -1 als Sentinel für „nicht ausgeglichen“ zurück und reichen Sie diesen Wert nach oben weiter. Sobald ein nicht ausgeglichener Knoten gefunden wird, kann die Suche frühzeitig beendet werden.
def is_balanced(root):
def check(node):
if not node:
return 0
left = check(node.left)
if left == -1:
return -1 # propagate early exit
right = check(node.right)
if right == -1:
return -1
if abs(left - right) > 1:
return -1 # unbalanced here
return 1 + max(left, right) # height if balanced
return check(root) != -1
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.left.left = TreeNode(5) # too deep on left
print(is_balanced(root)) # FalseDas Muster mit dem Sentinel-Rückgabewert
Das Zurückgeben eines Sentinel-Werts (-1 für nicht ausgeglichen oder ein spezielles Tupel) ist ein gängiges Muster, wenn eine DFS-Hilfsfunktion zwei Arten von Informationen signalisieren muss: das berechnete Ergebnis und ob eine Bedingung verletzt wurde. Statt Ausnahmen auszulösen oder globale Flags zu verwenden, kodieren Sie den Fehler im Rückgabetyp. Dieser Ansatz ist übersichtlich, vermeidet globalen Zustand und lässt sich natürlich mit anderen rekursiven Hilfsfunktionen kombinieren.
# General pattern: return (is_valid, computed_value)
def balanced_height(node):
if not node:
return True, 0
left_ok, left_h = balanced_height(node.left)
if not left_ok:
return False, 0 # short-circuit
right_ok, right_h = balanced_height(node.right)
if not right_ok:
return False, 0
balanced = abs(left_h - right_h) <= 1
return balanced, 1 + max(left_h, right_h)
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
ok, h = balanced_height(root)
print(ok, h) # True 2Durchmesser gemessen in Knoten oder Kanten
Lesen Sie die Aufgabenstellung genau: LeetCode #543 misst den Durchmesser in Kanten, während manche Aufgaben ihn in Knoten messen. Wenn Sie die Anzahl der Knoten benötigen, lautet der durch einen Knoten verlaufende Durchmesser height(left) + height(right) + 1 (addieren Sie 1 für den Knoten selbst). Für die Anzahl der Kanten lassen Sie +1 weg. Klären Sie dies vor dem Programmieren immer mit Ihrem Interviewer.
def diameter_in_nodes(root):
max_path = [0]
def dfs(node):
if not node:
return 0
left_h = dfs(node.left)
right_h = dfs(node.right)
# Path through this node in NODE count
nodes_through = left_h + right_h + 1
max_path[0] = max(max_path[0], nodes_through)
return 1 + max(left_h, right_h)
dfs(root)
return max_path[0]
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(diameter_in_nodes(root)) # 4 nodes: 4-2-1-3 or 5-2-1-3Pfadsumme: jeder Wurzel-Blatt-Pfad
Bei der Aufgabe zur Pfadsumme wird gefragt, ob die Summe eines Wurzel-Blatt-Pfads einem Zielwert entspricht. Verwenden Sie DFS und ziehen Sie den Wert des aktuellen Knotens vom Zielwert ab, während Sie nach unten gehen. Prüfen Sie an einem Blatt, ob der verbleibende Zielwert dem Wert des Blatts entspricht. Dies ist ein Preorder-DFS-Durchlauf, bei dem Sie die verbleibende Summe als Parameter übergeben – ein klassisches Beispiel für Rekursion von oben nach unten.
def has_path_sum(root, target):
if not root:
return False
# Leaf node: check if we've exactly hit the target
if not root.left and not root.right:
return root.val == target
remaining = target - root.val
return (has_path_sum(root.left, remaining) or
has_path_sum(root.right, remaining))
root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(8)
root.left.left = TreeNode(11)
root.left.left.left = TreeNode(7)
root.left.left.right = TreeNode(2)
print(has_path_sum(root, 22)) # True: 5+4+11+2=22Maximale Pfadsumme (schwierige Variante)
Die maximale Pfadsumme (LeetCode #124) ist deutlich schwieriger: Der Pfad kann an einem beliebigen Knoten beginnen und enden, nicht nur an der Wurzel oder einem Blatt, und Werte können negativ sein. Berücksichtigen Sie bei jedem Knoten vier Möglichkeiten: nur der Knoten selbst, Knoten + linker Teilpfad, Knoten + rechter Teilpfad oder Knoten + beide Teilpfade. Nur die ersten drei können nach oben an den Elternknoten weitergeführt werden; die vierte Möglichkeit ist ein endgültiger Kandidat für das globale Maximum.
def max_path_sum(root):
max_sum = [float('-inf')]
def gain(node):
if not node:
return 0
# Only take positive contributions
left = max(gain(node.left), 0)
right = max(gain(node.right), 0)
# Best path through this node (can't go both ways upward)
max_sum[0] = max(max_sum[0], node.val + left + right)
# Return the best single-branch gain for parent
return node.val + max(left, right)
gain(root)
return max_sum[0]
root = TreeNode(-10)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
print(max_path_sum(root)) # 42: 15+20+7AVL-Bäume und Selbstbalancierung
Ein AVL-Baum ist ein BST, der die Höhenbalance-Eigenschaft durch Rotationen nach Einfüge- und Löschoperationen aufrechterhält. Jeder Knoten speichert einen Balancefaktor (Höhe(rechts) - Höhe(links)), der in {-1, 0, 1} liegen muss. Wenn eine Verletzung auftritt, stellt eine einfache oder doppelte Rotation die Balance in O(1) Zeit wieder her. Dadurch bleibt die Gesamthöhe bei O(log n), und alle Operationen haben garantiert eine Laufzeit von O(log n).
# Balance factor = height(right) - height(left)
# AVL invariant: balance factor in {-1, 0, 1} for every node
# Four violation types and their fixes:
# LL (left-heavy left child): single right rotation
# RR (right-heavy right child): single left rotation
# LR (right-heavy left child): left rotate child, then right rotate root
# RL (left-heavy right child): right rotate child, then left rotate root
# Knowing this is enough for interviews; you rarely implement
# full AVL in an interview but must discuss the concept.
print('AVL maintains O(log n) height via rotations')Prüfen, ob ein Baum symmetrisch ist
Ein Binärbaum ist symmetrisch, wenn er ein Spiegelbild seiner selbst ist. Prüfen Sie dies rekursiv: Der Baum ist symmetrisch, wenn für jedes Paar entsprechender Knoten auf beiden Seiten der Achse die Werte gleich sind und sich ihre Teilbäume spiegeln. Definieren Sie eine Hilfsfunktion is_mirror(left, right), die Folgendes prüft: beide Null (in Ordnung), einer Null (nicht in Ordnung), gleiche Werte sowie spiegelbildliche innere und äußere Teilbäume.
def is_symmetric(root):
def is_mirror(left, right):
if not left and not right:
return True
if not left or not right:
return False
return (left.val == right.val and
is_mirror(left.left, right.right) and
is_mirror(left.right, right.left))
return is_mirror(root.left, root.right)
sym = TreeNode(1)
sym.left = TreeNode(2)
sym.right = TreeNode(2)
sym.left.left = TreeNode(3)
sym.right.right = TreeNode(3)
print(is_symmetric(sym)) # True
nosym = TreeNode(1)
nosym.left = TreeNode(2)
nosym.right = TreeNode(2)
nosym.left.right = TreeNode(3)
print(is_symmetric(nosym)) # FalseHöhe und Durchmesser gemeinsam betrachten
Das Postorder-Muster in einem einzigen Durchlauf, bei dem ein Hilfsverfahren gleichzeitig die Höhe zurückgibt und ein globales Ergebnis aktualisiert, lässt sich auf viele Probleme übertragen: den Durchmesser, die maximale Pfadsumme, die Prüfung der Balance, das Zählen von Good Nodes und weitere. Fragen Sie sich immer: „Welche Informationen benötigt der Elternknoten von jedem Kind?“ Das ist der Rückgabewert. „Welche Berechnung ist für diesen Knoten lokal?“ Diese aktualisiert die globale Antwort. Diese Zerlegung ist die entscheidende Fähigkeit für anspruchsvolle Baumprobleme.
# Reusable template for post-order dual-purpose DFS:
def tree_problem(root):
result = [float('-inf')] # or 0 depending on problem
def dfs(node):
if not node:
return 0 # base return (height, count, etc.)
left_val = dfs(node.left)
right_val = dfs(node.right)
# --- Update global result using both children ---
candidate = left_val + right_val # example: diameter
result[0] = max(result[0], candidate)
# --- Return info needed by PARENT ---
return 1 + max(left_val, right_val) # example: height
dfs(root)
return result[0]
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
print(tree_problem(root)) # diameter = 2Kurze Überprüfung
Testen Sie Ihr Verständnis der Konzepte aus Data Structures & Algorithms — Coding Interview Prep aus dieser Lektion.
Zusammenfassung der Lektion
In dieser Lektion haben Sie Folgendes gelernt: die Berechnung der Höhe mit rekursiver Postorder-DFS, die Berechnung des Durchmessers in einem einzigen O(n)-Durchlauf mit einem vielseitig einsetzbaren DFS-Hilfsverfahren sowie die Prüfung der Balance mit einem Sentinel-Wert zum vorzeitigen Abbruch. Als Nächstes behandeln wir Probleme mit Pfadsummen und den niedrigsten gemeinsamen Vorfahren.
Häufig gestellte Fragen
Ist die Lektion „Durchmesser, Höhe und balancierte Bäume“ kostenlos?
Ja — der vollständige Text von „Durchmesser, Höhe und balancierte Bäume“ 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 „Durchmesser, Höhe und balancierte Bäume“?
Berechnen Sie Durchmesser und Höhe eines Baums in einem einzigen DFS-Durchlauf mit einer Hilfsfunktion, die beide Werte zurückgibt, und prüfen Sie, ob der Baum höhenbalanciert ist. 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 3 von 4.
Wie lange dauert die Lektion „Durchmesser, Höhe und balancierte Bäume“?
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