Постановка задачи :

Вам дано двоичное дерево поиска (BST) целых чисел и целое число «K».

Ваша задача — найти и вернуть сумму первых «K» наименьших элементов BST.

Первая строка ввода содержит элементы дерева в порядке уровней, разделенные одним пробелом.

Если какой-либо узел не имеет левого или правого дочернего элемента, возьмите на его место -1.

Во второй строке записано одно целое число «K».

Пример ввода:

8 4 12 1 6 -1 -1 -1 -1 -1 7 -1 -1
4

Пример вывода:

18

Объяснение данного тестового примера:

Для данного дерева ‘K = 4’. Первые «4» наименьших элемента — это 1, 4, 6 и 7. Сумма трех наименьших узлов в BST = 1 + 4 + 6 + 7 = 18. Таким образом, вы должны вернуть «18» в качестве ответа.

Подход :

Неупорядоченный обход до первых «K» узлов

Выполняя неупорядоченный обход BST рекурсивно, вместе с «ROOT» передайте целое число «K» в качестве ссылки. Всякий раз, когда мы посещаем «ROOT» во время обхода по порядку, уменьшаем значение «K» на единицу и добавляем «ROOT->DATA» к сумме узлов до сих пор. Если в какой-то момент во время рекурсии «K» становится «0», мы посетили первые «K» узлов, поэтому остановите рекурсию. Функция inorderTraversal вычисляет сумму первых «K» наименьших узлов в BST, используя неупорядоченный обход.

«целое число inorderTraversal (BinaryTreeNode ROOT, целое число K)»:

  • Если «ROOT» равен «NULL», то «ROOT» не является допустимым узлом: верните 0 в качестве суммы.
  • Если «K» равно «0», то мы уже посетили первые «K» узлов: верните 0 в виде суммы.
  • Установите «SUM = inorderTraversal (ROOT-›LEFT, K)». Это сумма узлов в левом поддереве «ROOT».
  • Если «K» равно «0», то мы уже посетили первые «K» узлов при обходе левого поддерева «ROOT»: верните «SUM» в качестве суммы.
  • «СУММА += КОРЕНЬ->ДАННЫЕ». Добавьте данные в «ROOT» к сумме до сих пор.
  • «К-= 1». Поскольку мы посетили узел «ROOT», уменьшите «K» на единицу.
  • «СУММА += обход по порядку (ROOT-›RIGHT, K)». Добавьте сумму узлов в правом поддереве «ROOT» к «SUM».
  • Верните «SUM» как сумму первых «K» наименьших узлов BST в «ROOT».

АЛГОРИТМ:

  • «СУММ = inorderTraversal (ROOT, K)». Вычислите сумму первых «K» наименьших элементов в BST.
  • Верните «СУММ» в качестве ответа.

Временная сложность: O(N)
Пространственная сложность: O(N)

Код :

Спасибо за чтение

Placewit воспитывает лучших инженеров, предоставляя интерактивные занятия в классе и помогая им развивать свои навыки и попадать в замечательные компании.

Узнайте больше на Placewit. Следите за нами в Instagram и Facebook для ежедневного обучения.