Algorithmen und Datenstrukturen · Middle · Frage 38 von 75
Wie berechnet man rekursiv die maximale Tiefe eines Binärbaums?
function depth(node) {
if (!node) return 0;
// ?
}- 1
return depth(node.left) + depth(node.right); - 2
return 1 + Math.max(depth(node.left), depth(node.right)); - 3
return 1 + Math.min(depth(node.left), depth(node.right));
Antwort zeigen
Richtige Antwort: return 1 + Math.max(depth(node.left), depth(node.right));
Erklärung
Die Tiefe eines Knotens ist eins mehr als die seines tieferen Teilbaums, und ein leerer Teilbaum hat Tiefe 0. Beide Teilbäume zu addieren zählt Knoten, nicht die Tiefe. Die Kosten sind O(n), mit einer Rekursionstiefe gleich der Höhe.