Сумма всех узлов с меньшими значениями на расстоянии 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)