Вопрос:

Учитывая 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;
        
    }
};
  1. Функция minDiff() принимает два параметра: указатель на корень BST (Node* root) и целое число K. Возвращает минимальную абсолютную разницу.
  2. Внутри функции minDiff() есть рекурсивный подход к обходу BST и поиску минимальной абсолютной разницы. Переменная ans вначале инициализируется INT_MAX.
  3. Рекурсивный обход начинается с корневого узла. Если корневой узел существует (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)

Заключение:

Надеюсь, что решение окажется полезным и вам, ребята, понравилось. Давайте обсудим новые подходы. Пожалуйста, прокомментируйте, если у вас есть предложения и сомнения, которые необходимо развеять.

Удачного кодирования.