Постановка задачи :
Вам дано двоичное дерево поиска (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 для ежедневного обучения.