Bäume & BSTs
Die natürliche Heimat der Rekursion.
Bäume machen aus Rekursion eine Denkweise. Beherrsche die Traversierungen (Pre-, In-, Post- und Level-Order), die Invariante des binären Suchbaums und die rekursiven Muster für Tiefe, Balance und den niedrigsten gemeinsamen Vorfahren.
Lektionen in dieser Stufe
- 01
Baum-Traversierungen
FortgeschrittenPre-, In- und Post-Order-DFS plus Level-Order-BFS - die vier Wege, jeden Knoten zu besuchen, und wann welcher das richtige Werkzeug ist.
16 Min. - 02
Rekursiv auf Bäumen denken
FortgeschrittenDie Vorlage hinter den meisten Baumproblemen: löse für die Kinder, dann kombiniere - Tiefe, Knotenzahl und 'ist das balanciert?' folgen einer Form.
15 Min. - 03
Binäre Suchbäume
FortgeschrittenDie BST-Invariante (links < Knoten < rechts) gibt O(log n)-Suche, -Einfügen und -Löschen - und warum eine In-Order-Traversierung sortiert herauskommt.
15 Min. - 04
Niedrigster gemeinsamer Vorfahre
ExperteEin beliebtes Interviewproblem: finde den tiefsten Knoten, der Vorfahre zweier anderer ist - im einfachen Binärbaum und im BST.
13 Min. - 05
Balance, Heaps & Tries
ExperteWarum Balance zählt (und was ein selbstbalancierender Baum bringt), wie ein Heap ein Baum in einem Array ist und der Trie für Präfix-Probleme.
14 Min.