Algorithmuspro

Breitensuche im Baum

Durchlaufe einen Baum Ebene für Ebene und merke dir mit einer Queue, welcher Knoten als Nächstes dran ist.

Zeit: O(n)
Speicher: O(n)

// Schritt für Schritt

Schritt 1 / 15

1function levelOrder(root) {2  const queue = [root], out = [];3  while (queue.length > 0) {4    const node = queue.shift();5    out.push(node.val);6    if (node.left) queue.push(node.left);7    if (node.right) queue.push(node.right);8  }9  return out;10}

queue: = [4]
out: = []

Lege die Wurzel, 4, in die Queue.

Tipp: Mit den Pfeiltasten durch die Schritte gehen.

// pro-lektion

Den ganzen Durchlauf freischalten

Diese Lektion ist Teil von Pro. Pro schaltet jeden Schritt jeder Lektion frei, dazu Muster-Übungen und Fortschrittsauswertungen.

Preise ansehen

So funktioniert es

Breitensuche besucht jeden Knoten einer Ebene, bevor es eine Ebene tiefer geht. Eine Queue hält die Reihenfolge fest: Nimm den vordersten Knoten, gib ihn aus und stelle seine Kinder hinten an. Kinder reihen sich immer hinter alles ein, was schon wartet, deshalb ist eine Ebene ganz fertig, bevor die nächste beginnt. Dieselbe Idee findet den kürzesten Weg in einem ungewichteten Graphen. O(n) Zeit und O(n) Speicher für die Queue.

Dieses Muster erkennen üben →