Алгоритми та структури даних · Middle · Запитання 38 з 75
Як рекурсивно обчислити максимальну глибину бінарного дерева?
function depth(node) {
if (!node) return 0;
// ?
}- 1
return depth(node.left) + depth(node.right); - ✓Правильна відповідь:
return 1 + Math.max(depth(node.left), depth(node.right)); - 3
return 1 + Math.min(depth(node.left), depth(node.right));
Пояснення
Глибина вузла на одиницю більша за глибше з його піддерев, а порожнє піддерево має глибину 0. Сума обох піддерев рахувала б вузли, а не глибину. Вартість O(n), глибина рекурсії дорівнює висоті.