Максимальное среднее значение бинарного поддерева
Задача: дано бинарное дерево, необходимо написать алгоритм, который вернет максимальное среднее значение поддерева.
Справка:
- Поддерево — это любой узел этого дерева плюс всего его потомки.
- Среднее значение дерева — это сумма его значений, деленная на количество узлов.
Входные данные: root — корень бинарного дерева
Вывод: максимальное среднее значение поддерева.
Примеры:
Output: 6
Пояснение: Max[
- (5 + 6 + 1) / 3 = 4
- 6 / 1 = 6
- 1 / 1 = 1
] = 6
Разбор
Воспользуемся методом поиска в глубину (DFS). Для каждого узла мы рекурсивно запустим поиск в глубину и найдем кол-во дочерних узлов слева и справа, а также сумму этих значений. Далее определим среднее значение для текущего узла и сравним с результирующим максимальным значением.
Рекурсивная подфункция будет возвращать массив, где 1й элемент — это кол-во дочерних узлов, а 2й элемент — сумма значений дочерних узлов.
Детали реализации смотрите ниже.
Реализация
https://gist.github.com/unilecs/b7c21026a06afbb556188b59f494866e
