Сумма узлов на максимальной глубине двоичного дерева | Комплект 2

Опубликовано: 14 Января, 2022

Для данного корневого узла дерева найдите сумму всех листовых узлов, которые находятся на максимальной глубине от корневого узла.

Пример:

      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.

РЕКОМЕНДУЕМЫЕ СТАТЬИ