Пара с минимальной абсолютной разницей | BST
Опубликовано: 23 Января, 2022
Учитывая двоичное дерево поиска размером N> 1 , задача состоит в том, чтобы найти минимальную абсолютную разницу между любыми двумя узлами.
Примеры:
Вход:
5
/
3 7
/ /
2 4 6 8
Выход: 1
Разница между всеми последовательными узлами, если они отсортированы, равна 1.
Таким образом, ответ - 1.
Вход:
1
6
Выход: 5
Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.
Подход: мы знаем, что при обходе дерева двоичного поиска оно проходит в отсортированном порядке. Итак, для каждого узла мы найдем его отличие от предыдущего узла при обходе дерева по порядку. Если эта разница меньше предыдущей минимальной разницы, мы обновим предыдущую минимальную разницу. Ниже приведены шаги, которые необходимо выполнить:
- Создайте переменную prev, чтобы сохранить указатель на предыдущий узел в обходе по порядку.
- Создайте переменную ans, чтобы сохранить минимальную разницу.
- Для каждого узла в обходе по порядку сравните его абсолютную разницу с предыдущим узлом и обновите минимальную абсолютную разницу, найденную на данный момент.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Node of the binary tree struct node { int data; node* left; node* right; node(int data) { this->data = data; left = NULL; right = NULL; } }; // Function for in-order traversal of the tree void inorder(node* curr, node*& prev, int& ans) { // Base-case if (curr == NULL) return; // Calling in-order on the left sub-tree inorder(curr->left, prev, ans); if (prev != NULL) ans = min(curr->data - prev->data, ans); prev = curr; // Calling in-order on the right sub-tree inorder(curr->right, prev, ans); } // Function to return the minimum // difference between any two nodes // of the given binary search tree int minDiff(node* root) { // Pointer to previous node in the // in-order traversal of the BST node* prev = NULL; // To store the final ans int ans = INT_MAX; // Call in-order for the BST inorder(root, prev, ans); // Returning the final answer return ans; } // Driver code int main() { node* root = new node(5); root->left = new node(3); root->right = new node(7); root->left->left = new node(2); root->left->right = new node(4); root->right->left = new node(6); root->right->right = new node(8); cout << minDiff(root); return 0; } |
Java
// Java implementation of the approach import java.util.*; class GFG { // Node of the binary tree static class node { int data; node left; node right; node(int data) { this.data = data; left = null; right = null; } }; static node prev;static int ans; // Function for in-order traversal of the tree static void inorder(node curr) { // Base-case if (curr == null) return; // Calling in-order on the left sub-tree inorder(curr.left); if (prev != null) ans = Math.min(curr.data - prev.data, ans); prev = curr; // Calling in-order on the right sub-tree inorder(curr.right); } // Function to return the minimum // difference between any two nodes // of the given binary search tree static int minDiff(node root) { // Pointer to previous node in the // in-order traversal of the BST prev = null; // To store the final ans ans = Integer.MAX_VALUE; // Call in-order for the BST inorder(root); // Returning the final answer return ans; } // Driver code public static void main(String[] args){ node root = new node(5); root.left = new node(3); root.right = new node(7); root.left.left = new node(2); root.left.right = new node(4); root.right.left = new node(6); root.right.right = new node(8); System.out.println(minDiff(root)); }} // This code is contributed by 29AjayKumar |
C#
// C# implementation of the approachusing System; class GFG { // Node of the binary tree public class node { public int data; public node left; public node right; public node(int data) { this.data = data; left = null; right = null; } }; static node prev;static int ans; // Function for in-order traversal of the tree static void inorder(node curr) { // Base-case if (curr == null) return; // Calling in-order on the left sub-tree inorder(curr.left); if (prev != null) ans = Math.Min(curr.data - prev.data, ans); prev = curr; // Calling in-order on the right sub-tree inorder(curr.right); } // Function to return the minimum // difference between any two nodes // of the given binary search tree static int minDiff(node root) { // Pointer to previous node in the // in-order traversal of the BST prev = null; // To store the final ans ans = int.MaxValue; // Call in-order for the BST inorder(root); // Returning the final answer return ans; } // Driver code public static void Main(String[] args){ node root = new node(5); root.left = new node(3); root.right = new node(7); root.left.left = new node(2); root.left.right = new node(4); root.right.left = new node(6); root.right.right = new node(8); Console.WriteLine(minDiff(root)); }} // This code is contributed by PrinciRaj1992 |
Другой подход с O (1) космической сложностью:
Сложность времени: O (N)
Дополнительное пространство: O (1)
Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .
Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.