Постановка задачи :
Вам дано бинарное дерево целых чисел. Ваша задача — вычислить сумму всех листовых узлов, присутствующих на самом глубоком уровне этого бинарного дерева. Если таких узлов нет, выведите 0.
ПРИМЕЧАНИЕ. Самый глубокий уровень бинарного дерева — это уровень, который находится на максимальной глубине от корневого узла.
Ввод:
71 2 16 110 -1 -1 5 -1 -1 -1 -1
Вывод:
115
Подход :
Обход порядка уровней
Идея состоит в том, чтобы выполнить обход заданного бинарного дерева в порядке уровней от корневого узла. Узлы, присутствующие на самом глубоком уровне, будут обрабатываться последними, поскольку мы обрабатываем дерево уровень за уровнем.
Вот полный алгоритм-
Временная сложность — O(N)
Пространственная сложность — O(N)
Код :
Спасибо за чтение
Placewit воспитывает лучших инженеров, предоставляя интерактивные занятия в классе и помогая им развивать свои навыки и попадать в замечательные компании.
Узнайте больше на Placewit. Следите за нами в Instagram и Facebook для ежедневного обучения.
