Вопрос:
Учитывая BST и целое число. Найдите наименьшую абсолютную разницу между любым значением узла BST и заданным целым числом.
Пример 1:
Input: 10 / \ 2 11 / \ 1 5 / \ 3 6 \ 4 K = 13 Output: 2 Explanation: K=13. The node that has value nearest to K is 11. so the answer is 2
Пример 2:
Input: 8 / \ 1 9 \ \ 4 10 / 3 K = 9 Output: 0 Explanation: K=9. The node that has value nearest to K is 9. so the answer is 0.
Ваша задача
Вам не нужно ничего читать или печатать. Ваша задача состоит в том, чтобы завершить функциюminDiff(), которая принимает корень BST и целое число K в качестве входных данных и возвращает минимальную абсолютную разницу между любым значением узла BST и целым числом K.
Ожидаемая временная сложность:O(высота BST).
Ожидаемое вспомогательное пространство:O(высота BST).
Ограничения:
1 ‹= количество узлов ‹= 105
1 ‹=данные‹= 105
Решение:
Подход:
Здесь мы следуем обычному обходу двоичного дерева поиска, то есть мы посещаем левый узел, если корневые данные меньше k, и посещаем правый узел, если корневые данные больше k. Таким образом, мы рассчитываем абсолютную разницу при каждом посещении.
Код:
/* Tree Node struct Node { int data; Node *left; Node *right; Node(int val) { data = val; left = right = NULL; } }; */ class Solution { public: int ans=INT_MAX; //Function to find the least absolute difference between any node //value of the BST and the given integer. int minDiff(Node *root, int K) { //Your code here if(root){ if(root->data == K){ ans = 0; }else if(root->data > K){ ans = min(ans, abs(root->data - K)); minDiff(root->left, K); }else{ ans = min(ans, abs(root->data - K)); minDiff(root->right, K); } } return ans; } };
- Функция
minDiff()
принимает два параметра: указатель на корень BST (Node* root
) и целое числоK
. Возвращает минимальную абсолютную разницу. - Внутри функции
minDiff()
есть рекурсивный подход к обходу BST и поиску минимальной абсолютной разницы. Переменнаяans
вначале инициализируетсяINT_MAX
. - Рекурсивный обход начинается с корневого узла. Если корневой узел существует (
if (root)
), он проверяет три случая:
- Если значение корневого узла равно
K
, минимальная абсолютная разница равна 0 (ans = 0
). - Если значение корневого узла больше
K
, оно обновляет переменнуюans
минимумом текущегоans
и абсолютной разницей между значением корневого узла иK
. Затем он рекурсивно вызываетminDiff()
в левом поддереве (minDiff(root->left, K)
). - Если значение корневого узла меньше
K
, оно обновляет переменнуюans
минимумом текущегоans
и абсолютной разницей между значением корневого узла иK
. Затем он рекурсивно вызываетminDiff()
в правом поддереве (minDiff(root->right, K)
).
4. Наконец, функция возвращает минимальную абсолютную разницу ans
.
Временная сложность: O (log N). В самом худшем случае, т. е. с искаженным двоичным деревом, тогда в худшем случае будет O (N).
Космическая сложность: O(1)
Заключение:
Надеюсь, что решение окажется полезным и вам, ребята, понравилось. Давайте обсудим новые подходы. Пожалуйста, прокомментируйте, если у вас есть предложения и сомнения, которые необходимо развеять.
Удачного кодирования.