BST und In-Order-Eigenschaften validieren
Validieren Sie einen Binärbaum als BST mit Min-/Max-Grenzen, die durch den Baum weitergegeben werden, und prüfen Sie, ob die In-Order-Traversierung eine sortierte Sequenz erzeugt.
BST und In-Order-Eigenschaften validieren ist eine kostenlose Coding 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 Coding Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Das Problem der BST-Validierung
Validate BST (LeetCode #98) ist eine klassische Aufgabe in Vorstellungsgesprächen, die viele Kandidaten vor Probleme stellt. Der naive Ansatz prüft nur, ob der Wert jedes Knotens größer als der seines linken Kindes und kleiner als der seines rechten Kindes ist. Diese lokale Prüfung ist jedoch unzureichend. Ein Knoten in einem Teilbaum kann die lokale Regel erfüllen und trotzdem die globale BST-Eigenschaft verletzen. Die korrekte Lösung gibt Min-/Max-Grenzen im Baum nach unten weiter.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# Why local check fails:
# 5
# / \
# 1 4
# / \
# 3 6
# Node 4's children (3, 6) satisfy local rule,
# but 4 < 5 and is in the RIGHT subtree -- BST violated!
print('Local check is insufficient -- use min/max bounds')Ansatz mit Min-/Max-Grenzen
Geben Sie untere und obere Grenzen in der Rekursion weiter. Prüfen Sie an jedem Knoten, ob low < node.val < high gilt. Aktualisieren Sie beim rekursiven Aufruf für den linken Teilbaum die obere Grenze auf node.val (der linke Teilbaum muss kleiner sein). Aktualisieren Sie beim Aufruf für den rechten Teilbaum die untere Grenze auf node.val (der rechte Teilbaum muss größer sein). Beginnen Sie mit low = -infinity und high = +infinity.
def is_valid_bst(root, low=float('-inf'), high=float('inf')):
if not root:
return True
if not (low < root.val < high):
return False
return (is_valid_bst(root.left, low, root.val) and
is_valid_bst(root.right, root.val, high))
# Valid BST:
valid = TreeNode(5)
valid.left = TreeNode(3)
valid.right = TreeNode(7)
print(is_valid_bst(valid)) # True
# Invalid BST (3 is in wrong subtree conceptually):
invalid = TreeNode(5)
invalid.left = TreeNode(1)
invalid.right = TreeNode(4)
invalid.right.left = TreeNode(3)
invalid.right.right = TreeNode(6)
print(is_valid_bst(invalid)) # False (4 < 5 in right subtree)Validierung durch Inorder-Traversierung
Ein alternativer Validierungsansatz nutzt die sortierte Inorder-Eigenschaft des BST: Sammeln Sie die Inorder-Folge und prüfen Sie, ob sie streng monoton steigt. Dieser Ansatz ist elegant und leicht nachzuvollziehen. Er benötigt jedoch O(n) zusätzlichen Speicher zum Speichern der Folge. Eine optimierte Variante verwendet während der Traversierung nur einen einzelnen prev-Zeiger, um jedes Wertepaar zu prüfen, ohne die gesamte Folge zu speichern.
def is_valid_bst_inorder(root):
prev = [float('-inf')]
def inorder(node):
if not node:
return True
if not inorder(node.left):
return False
if node.val <= prev[0]: # not strictly increasing
return False
prev[0] = node.val
return inorder(node.right)
return inorder(root)
valid = TreeNode(5)
valid.left = TreeNode(3)
valid.right = TreeNode(7)
valid.left.left = TreeNode(1)
valid.left.right = TreeNode(4)
print(is_valid_bst_inorder(valid)) # True
invalid = TreeNode(5)
invalid.left = TreeNode(6) # 6 > 5 in left subtree!
print(is_valid_bst_inorder(invalid)) # FalseVergleich beider Validierungsansätze
Der Ansatz mit Min-/Max-Grenzen benötigt O(n) Zeit und O(h) Speicher (nur für die Grenzen auf dem Aufruf-Stack). Der Ansatz mit dem Inorder-prev-Zeiger benötigt ebenfalls O(n) Zeit und O(h) Speicher. Beide Ansätze sind optimal. Der Min-/Max-Ansatz ist allgemeiner und lässt sich sauber auf Aufgaben mit zusätzlichen Bedingungen erweitern. Seien Sie in Vorstellungsgesprächen darauf vorbereitet, beide Ansätze vorzustellen und ihre Vor- und Nachteile zu diskutieren – die Kenntnis von Alternativen ist ein starkes Signal.
# Both approaches:
# Time: O(n) -- visit each node once
# Space: O(h) -- call stack depth
# h = O(log n) balanced, O(n) skewed
# When to choose which:
# min/max bounds:
# - Cleaner for trees with constraints beyond BST
# - No global state (purely functional)
# in-order prev:
# - More intuitive (sorted sequence check)
# - Easier to convert to iterative with a stack
print('Both O(n) time, O(h) space -- choose by clarity')BST wiederherstellen: Zwei vertauschte Knoten
Recover BST (LeetCode #99) repariert einen BST, in dem genau zwei Knoten vertauscht wurden. Bei einer korrekt geordneten BST ergibt die Inorder-Traversierung eine sortierte Folge. Wenn zwei Knoten vertauscht wurden, gibt es eine oder zwei Verletzungen, bei denen prev.val > current.val gilt. Der erste Knoten der ersten Verletzung und der zweite Knoten der letzten Verletzung sind die beiden falsch platzierten Knoten – vertauschen Sie ihre Werte.
def recover_tree(root):
first = second = prev = None
def inorder(node):
nonlocal first, second, prev
if not node:
return
inorder(node.left)
if prev and prev.val > node.val:
if not first:
first = prev # first violator
second = node # always update second
prev = node
inorder(node.right)
inorder(root)
# Swap values of the two misplaced nodes
if first and second:
first.val, second.val = second.val, first.val
root = TreeNode(3)
root.left = TreeNode(1)
root.right = TreeNode(4)
root.right.left = TreeNode(2) # 2 and 3 are swapped
recover_tree(root)
print(root.val, root.right.left.val) # 2, 3 (fixed)BST durch Inorder-Traversierung in ein sortiertes Array umwandeln
Ein BST in ein sortiertes Array umzuwandeln ist trivial: Führen Sie eine Inorder-Traversierung durch und sammeln Sie die Werte. Diese Operation benötigt O(n) Zeit und O(n) Speicher und ist eine schnelle Möglichkeit, Algorithmen für sortierte Arrays (binäre Suche, zwei Zeiger) auf BST-Daten anzuwenden. Sie dient häufig als Zwischenschritt bei mehrteiligen BST-Aufgaben wie „zwei BSTs zusammenführen“ oder „den Median eines BST finden“.
def bst_to_sorted_array(root):
result = []
def inorder(node):
if not node:
return
inorder(node.left)
result.append(node.val)
inorder(node.right)
inorder(root)
return result
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
root.right.left = TreeNode(5)
root.right.right = TreeNode(7)
print(bst_to_sorted_array(root)) # [1, 2, 3, 4, 5, 6, 7]Zwei BSTs zusammenführen
Um zwei BSTs zu einem sortierten Array zusammenzuführen, wandeln Sie jeden BST in O(n) bzw. O(m) in ein sortiertes Array um und führen Sie die beiden sortierten Arrays anschließend mit dem Merge-Schritt von Merge-Sort in O(n+m) zusammen. Die Gesamtzeit beträgt O(n+m). Wenn das Ergebnis ein balancierter BST sein soll, übergeben Sie das zusammengeführte sortierte Array an den Algorithmus zur Umwandlung eines sortierten Arrays in einen BST. Diese Zerlegung in einfache Teilprobleme ist ein Kennzeichen einer klaren, für Vorstellungsgespräche geeigneten Lösung.
def merge_two_bsts(root1, root2):
def inorder(node, arr):
if not node:
return
inorder(node.left, arr)
arr.append(node.val)
inorder(node.right, arr)
arr1, arr2 = [], []
inorder(root1, arr1)
inorder(root2, arr2)
# Merge two sorted arrays
merged = []
i = j = 0
while i < len(arr1) and j < len(arr2):
if arr1[i] <= arr2[j]:
merged.append(arr1[i]); i += 1
else:
merged.append(arr2[j]); j += 1
merged.extend(arr1[i:])
merged.extend(arr2[j:])
return merged
r1 = TreeNode(2); r1.left = TreeNode(1); r1.right = TreeNode(4)
r2 = TreeNode(3); r2.left = TreeNode(0); r2.right = TreeNode(5)
print(merge_two_bsts(r1, r2)) # [0, 1, 2, 3, 4, 5]Knoten im Wertebereich eines BST zählen
Zählen Sie, wie viele Knoten Werte im Bereich [low, high] haben. Ein vollständiger Inorder-Durchlauf benötigt O(n). Die BST-bewusste Variante schneidet Teilbäume ab: Wenn der Wert des aktuellen Knotens kleiner als low ist, muss der linke Teilbaum nicht geprüft werden, da alle seine Werte ebenfalls kleiner als low sind. Ebenso wird der rechte Teilbaum abgeschnitten, wenn der aktuelle Wert größer als high ist. Im Durchschnitt beträgt die Komplexität O(log n + k), wobei k die Anzahl der passenden Knoten ist.
def range_sum_bst(root, low, high):
if not root:
return 0
total = 0
if low <= root.val <= high:
total += root.val
if root.val > low: # left subtree may have values >= low
total += range_sum_bst(root.left, low, high)
if root.val < high: # right subtree may have values <= high
total += range_sum_bst(root.right, low, high)
return total
root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(15)
root.left.left = TreeNode(3)
root.left.right = TreeNode(7)
root.right.right = TreeNode(18)
print(range_sum_bst(root, 7, 15)) # 7 + 10 + 15 = 32Doppelte Werte und strikte vs. nicht-strikte BSTs
Die Standardinvariante eines BST verwendet strikte Ungleichungen: Werte im linken Teilbaum sind strikt kleiner und Werte im rechten Teilbaum strikt größer. Einige Aufgaben erlauben doppelte Werte und ordnen sie dem linken Teilbaum (left <= root) oder dem rechten Teilbaum (root < right) zu. Prüfen Sie bei der Validierung von BSTs immer die Definition in der Aufgabenstellung. Der Ansatz mit Min-/Max-Grenzen unterstützt beide Varianten, indem Sie anpassen, ob die Grenzprüfung strikt oder inklusiv erfolgt.
# Strict BST (LeetCode default): left < root < right
def is_valid_strict(root, lo=float('-inf'), hi=float('inf')):
if not root:
return True
if not (lo < root.val < hi): # STRICT inequalities
return False
return (is_valid_strict(root.left, lo, root.val) and
is_valid_strict(root.right, root.val, hi))
# Non-strict BST (allows duplicates in right): left <= root < right
def is_valid_nonstrict(root, lo=float('-inf'), hi=float('inf')):
if not root:
return True
if not (lo <= root.val < hi): # NOTE: <= for left side
return False
return (is_valid_nonstrict(root.left, lo, root.val + 1) and
is_valid_nonstrict(root.right, root.val, hi))
print('Always clarify strict vs non-strict with interviewer')Inorder als universelles BST-Werkzeug
Die Inorder-Traversierung ist das Schweizer Taschenmesser für BST-Aufgaben. Wann immer eine BST-Aufgabe nach sortierter Reihenfolge, dem k-ten Element, Bereichsabfragen oder Eigenschaften einer Folge fragt, sollten Sie prüfen, ob eine Inorder-Traversierung (oder ihre Umkehrung) die Lösung liefert. Die meisten BST-spezifischen Aufgaben lassen sich darauf reduzieren: in sortierter Reihenfolge traversieren und bei jedem Schritt etwas ausführen. Diese Zuordnung schnell zu erkennen ist eine wichtige Fähigkeit in Vorstellungsgesprächen.
# Problems solved elegantly with in-order:
# 1. Validate BST: check prev <= curr during in-order
# 2. Kth smallest: count k steps in in-order
# 3. Kth largest: count k steps in REVERSE in-order
# 4. Closest value to target: find crossover in in-order
# 5. BST to sorted array: collect in-order into list
# 6. Recover BST: find 1-2 violations in in-order
# 7. Sum of range [lo, hi]: accumulate during in-order
# The key insight: in-order visits BST nodes in sorted order.
# All sorted-order reasoning translates to in-order DFS.
print('In-order = sorted access = foundation of BST reasoning')Nächstgelegener Wert im BST
Finden Sie den Knoten, dessen Wert einem gegebenen Zielwert am nächsten liegt. Nutzen Sie die Ordnung des BST: Beginnen Sie an der Wurzel, speichern Sie den bisher nächstgelegenen Wert und bewegen Sie sich in Richtung des Zielwerts (gehen Sie nach links, wenn der Zielwert kleiner ist, und nach rechts, wenn er größer ist). Dieser Ansatz benötigt O(h) Zeit, ist effizienter als eine Inorder-Traversierung und zeigt, wie sich mithilfe der BST-Eigenschaft der Suchraum effektiv einschränken lässt.
def closest_value(root, target):
closest = root.val
curr = root
while curr:
if abs(curr.val - target) < abs(closest - target):
closest = curr.val
if target < curr.val:
curr = curr.left
elif target > curr.val:
curr = curr.right
else:
break # exact match
return closest
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(5)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
print(closest_value(root, 3.714286)) # 4Kurzer 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 BST-Validierung mit Min-/Max-Grenzen (wodurch die problematische lokale Prüfung vermieden wird), die Alternative mit dem Inorder-prev-Zeiger zur Validierung sowie Inorder-Traversierung als universelles BST-Werkzeug für Bereichssummen, nächstgelegene Werte und Zusammenführungsoperationen. Als Nächstes nutzen wir Inorder-Eigenschaften von BSTs, um das k-kleinste Element zu finden.
Häufig gestellte Fragen
Ist die Lektion „BST und In-Order-Eigenschaften validieren“ kostenlos?
Ja — der vollständige Text von „BST und In-Order-Eigenschaften validieren“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Coding Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „BST und In-Order-Eigenschaften validieren“?
Validieren Sie einen Binärbaum als BST mit Min-/Max-Grenzen, die durch den Baum weitergegeben werden, und prüfen Sie, ob die In-Order-Traversierung eine sortierte Sequenz erzeugt. Du übst Coding 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 Coding Interview Prep zu starten?
Keine Vorkenntnisse erforderlich. Coding 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 „BST und In-Order-Eigenschaften validieren“?
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 Coding Interview Prep-Lektion Code schreiben und ausführen?
Ja. Jede Coding 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
- BST-Einfügen und -Suchen
- BST-Löschen: drei Fälle
- BST und In-Order-Eigenschaften validieren
- K-kleinstes Element, Bereichssumme und BST zu sortiertem Array