Algorytmy i struktury danych · Middle · Pytanie 38 z 75
Jak rekurencyjnie policzyć maksymalną głębokość drzewa binarnego?
function depth(node) {
if (!node) return 0;
// ?
}- 1
return depth(node.left) + depth(node.right); - ✓Poprawna odpowiedź:
return 1 + Math.max(depth(node.left), depth(node.right)); - 3
return 1 + Math.min(depth(node.left), depth(node.right));
Wyjaśnienie
Głębokość węzła jest o jeden większa od głębszego z jego poddrzew, a puste poddrzewo ma głębokość 0. Suma obu poddrzew liczyłaby węzły, a nie głębokość. Koszt to O(n), a głębokość rekurencji równa się wysokości.