Сумма всех узлов с меньшими значениями на расстоянии K от заданного узла в BST

Опубликовано: 21 Сентября, 2022

Учитывая двоичное дерево поиска, целевой узел в BST и целочисленное значение K , задача состоит в том, чтобы найти сумму всех узлов, которые находятся на расстоянии K от целевого узла, значение которого меньше целевого узла.

Примеры:

Input: target = 7, K = 2

Output: 11
Explanation:
The nodes at a  distance K(= 2) from the node 7 is 1, 4, and 6. Therefore, the sum of nodes is 11.

Input: target = 5, K = 1

Output: 4

Подход: Данную проблему можно решить, выполнив обход в глубину на расстоянии K ниже целевого узла и выполнив обход в глубину вверх на расстоянии K от целевого узла. Выполните следующие шаги, чтобы решить проблему:

  • Определите функцию kDistanceDownSum(root, k, &sum) и выполните следующие шаги:
    • В базовом случае проверьте, является ли корень nullptr и k меньше 0 , а затем вернитесь из функции.
    • Если значение k равно 0 , то добавьте root->val к переменной sum и вернитесь.
    • Вызовите одну и ту же функцию kDistanceDownSum(root->left, k-1, sum) и kDistanceDownSum(root->right, k – 1, sum) для левого и правого поддеревьев.
  • В базовом случае проверьте, является ли корень nullptr , затем верните -1 .
  • Если корень совпадает с target , то вызовите функцию kDistanceDownSum(root->left, k – 1, sum), чтобы вычислить сумму для первого типа узлов и вернуть 0 (второй тип узлов невозможен).
  • Инициализируйте переменную dl как -1 и, если цель меньше корня, затем установите значение dl как значение, возвращаемое функцией kDistanceSum(root->left, target k, sum) .
  • Если значение dl не равно -1 , то если sum равно (dl + 1) , то добавьте значение root->data к сумме и затем верните -1 .
  • Точно так же инициализируйте переменную dr как -1 и, если цель больше, чем корень , затем обновите значение dr до значения, возвращаемого kDistanceSum(root->right, target k, sum) .
  • Если значение dr не равно -1 , то если значение sum равно (dr + 1) , то к сумме добавляется значение root->data . В противном случае вызовите функцию kDistanceDownSum(root->left, k – dr – 2, sum) и верните (1 + dr) .
  • После выполнения вышеуказанных шагов выведите значение ans в виде результирующей суммы.

Ниже приведена реализация вышеуказанного подхода:

Сложность времени:
Вспомогательное пространство: O(1)

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