Сумма узлов на максимальной глубине двоичного дерева | Комплект 2
Для данного корневого узла дерева найдите сумму всех листовых узлов, которые находятся на максимальной глубине от корневого узла.
Пример:
1 / 2 3 / / 4 5 6 7 Ввод: корень (верхнего дерева) Выход: 22 Объяснение: Узлы на максимальной глубине: 4, 5, 6, 7. Итак, сумма этих узлов = 22
Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.
В предыдущей статье мы обсуждали рекурсивное решение, которое сначала находит максимальный уровень, а затем находит сумму всех узлов, присутствующих на этом уровне.
В этой статье мы увидим рекурсивное решение без определения высоты или глубины. Идея состоит в том, что при обходе узлов сравнивайте уровень узла с max_level (максимальный уровень до текущего узла). Если текущий уровень превышает максимальный уровень, обновите max_level как текущий уровень. Если максимальный уровень и текущий уровень совпадают, добавьте корневые данные к текущей сумме, в противном случае, если уровень меньше max_level, ничего не делать.
Ниже представлена реализация описанного выше подхода:
Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .
Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.