Tiefensuche im Baum
Durchlaufe einen binären Suchbaum in-order: linker Teilbaum, dann der Knoten, dann der rechte Teilbaum.
- Zeit
- O(n)
- Speicher
- O(h)
// Schritt für Schritt
1function inorder(node, out) {2 if (node === null) return;3 inorder(node.left, out);4 out.push(node.val);5 inorder(node.right, out);6}- out
- = []
- 4
- 2
- 6
- 1
- 3
- 5
- 7
Bei 4: zuerst in den linken Teilbaum.
Den ganzen Durchlauf freischalten
Diese Lektion ist Teil von Pro. Pro schaltet jeden Schritt jeder Lektion frei, dazu Muster-Übungen und Fortschrittsauswertungen.
Preise ansehenSo funktioniert es
Tiefensuche geht so tief wie möglich, bevor sie zurückgeht. Der In-order-Durchlauf tut das in fester Reihenfolge: zuerst der ganze linke Teilbaum, dann der Knoten selbst, dann der rechte Teilbaum. Das Zurückgehen übernimmt die Rekursion von allein, weil jeder Aufruf zu seinem Elternknoten zurückkehrt. Bei einem binären Suchbaum liefert diese Reihenfolge die Werte sortiert. Jeder Knoten wird einmal besucht: O(n) Zeit und O(h) Speicher für den Aufrufstapel, wobei h die Höhe des Baums ist.
Dieses Muster erkennen üben →