Максимальная глубина бинарного дерева

Сложность: 🟢 Легкая

ℹ️ Описание

Найдите максимальную глубину бинарного дерева.

Максимальная глубина бинарного дерева — это количество узлов на самом длинном пути от корневого узла до самого дальнего листового узла.

⚠️ Ограничения

— Количество узлов в дереве может быть от 0 до 10000
— Значение каждого узла находится в диапазоне от -100 до 100

✅ Решение

Для решения задачи нам достаточно реализовать простой поиск в глубину DFS (Depth First Search).

Реализуем дополнительную рекурсивную функцию dfs, которая принимает на вход два аргумента:
— текущий узел дерева node
— текущую глубину погружения level

В качестве ответа функция будет возвращать максимальную глубину ветки дерева.

Если в функции dfs на вход пришла пустая нода, то это означает, что мы опустились ниже последнего листового узла в этой ветке, т. е. мы спустились до ее конца. В этом случае мы возвращаем из функции level в качестве ответа, так как он обозначает текущую глубину ветки.

Если же нода присутствует, то нам нужно найти в какой из ее дочерних веток максимальная глубина. Для этого мы запускаем рекурсивный поиск по левой и правой дочерней ветке и передаем в функцию увеличенный на 1 уровень глубины. Получив два числа для левой и правой ветки, нам нужно выбрать максимальное и вернуть его в качестве ответа.

В самом конце нам остается вызвать из основной функции maxDepth наш dfs поиск, определив начальную глубину равную 0.

Посмотреть реализацию в блоге

#tree #binary_tree #easy