Найдите минимальную абсолютную разницу в двух разных BST
Опубликовано: 23 Января, 2022
Учитывая 2 дерева двоичного поиска, выберите по одному узлу из каждого дерева так, чтобы их абсолютная разница была минимально возможной. Предположим, что у каждого BST есть хотя бы один узел.
Примеры:
Ввод: N 1 = 7, N 2 = 2
BST1:
5
/
3 7
/ /
2 4 6 8
BST2:
11
13
Выход: 3
8 - наибольшее число в первом BST
а 11 - наименьшее во втором.
Таким образом, окончательный ответ будет 11-8 = 3.
Ввод: N 1 = 4, N 2 = 2
BST1:
3
/
2 4
14
BST2:
7
13
Выход: 1
Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.
Approach:
The idea is to use the two-pointer technique and iterating the pointers using the following steps.
- Create forward iterators for both the BST’s. Let’s say that the value of nodes they are pointing at are v1 and v2 respectively.
- Now at each step:
- Update final ans as min(ans, abs(v1-v2)) .
- If v1 < v2, move iterator of first BST else move the iterator of the second BST.
- Repeat above steps till both the BST’s are pointing to a valid nodes.
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Node of Binary treestruct node { int data; node* left; node* right; node(int data) { this->data = data; left = NULL; right = NULL; }};// Function to iterate to the// next element of the BSTvoid next(stack<node*>& it){ node* curr = it.top()->right; it.pop(); while (curr != NULL) it.push(curr), curr = curr->left;}// Function to find minimum differenceint minDiff(node* root1, node* root2){ // Iterator for two Binary Search Trees stack<node *> it1, it2; // Initializing first iterator node* curr = root1; while (curr != NULL) it1.push(curr), curr = curr->left; // Initializing second iterator curr = root2; while (curr != NULL) it2.push(curr), curr = curr->left; // Variable to store final answer int ans = INT_MAX; // Two pointer technique while (it1.size() and it2.size()) { // value it1 and it2 are pointing to int v1 = it1.top()->data; int v2 = it2.top()->data; // Updating final answer ans = min(abs(v1 - v2), ans); // Case when v1 < v2 if (v1 < v2) next(it1); else next(it2); } // Return ans return ans;}// Driver codeint main(){ // BST-1 /* 5 / 3 7 / / 2 4 6 8 */ node* root2 = new node(5); root2->left = new node(3); root2->right = new node(7); root2->left->left = new node(2); root2->left->right = new node(4); root2->right->left = new node(6); root2->right->right = new node(8); // BST-2 /* 11 15 */ node* root1 = new node(11); root1->right = new node(15); cout << minDiff(root1, root2); return 0;} |
Java
// Java implementation of the approachimport java.util.*;class GFG{// Node of Binary treestatic class node{ int data; node left; node right; node(int data) { this.data = data; left = null; right = null; }};// Function to iterate to the// next element of the BSTstatic void next(Stack<node> it){ node curr = it.peek().right; it.pop(); while (curr != null) { it.push(curr); curr = curr.left; }}// Function to find minimum differencestatic int minDiff(node root1, node root2){ // Iterator for two Binary Search Trees Stack<node> it1 = new Stack<node>(); Stack<node> it2 = new Stack<node>(); // Initializing first iterator node curr = root1; while (curr != null) { it1.push(curr); curr = curr.left; } // Initializing second iterator curr = root2; while (curr != null) { it2.push(curr); curr = curr.left; } // Variable to store final answer int ans = Integer.MAX_VALUE; // Two pointer technique while (it1.size() > 0 && it2.size() > 0) { // value it1 and it2 are pointing to int v1 = it1.peek().data; int v2 = it2.peek().data; // Updating final answer ans = Math.min(Math.abs(v1 - v2), ans); // Case when v1 < v2 if (v1 < v2) next(it1); else next(it2); } // Return ans return ans;}// Driver codepublic static void main(String[] args){ // BST-1 /* 5 / 3 7 / / 2 4 6 8 */ node root2 = new node(5); root2.left = new node(3); root2.right = new node(7); root2.left.left = new node(2); root2.left.right = new node(4); root2.right.left = new node(6); root2.right.right = new node(8); // BST-2 /* 11 15 */ node root1 = new node(11); root1.right = new node(15); System.out.println(minDiff(root1, root2));}}// This code is contributed by 29AjayKumar |
Python3
# Python3 implementation of the approachimport sys# Node of the binary treeclass node: def __init__ (self, key): self.data = key self.left = None self.right = None# Function to iterate to the# next element of the BSTdef next(it): curr = it[-1].right del it[-1] while (curr != None): it.append(curr) curr = curr.left return it# Function to find minimum differencedef minDiff(root1, root2): # Iterator for two Binary Search Trees it1, it2 = [], [] # Initializing first iterator curr = root1 while (curr != None): it1.append(curr) curr = curr.left # Initializing second iterator curr = root2 while (curr != None): it2.append(curr) curr = curr.left # Variable to store final answer ans = sys.maxsize # Two pointer technique while (len(it1) > 0 and len(it2) > 0): # Value it1 and it2 are pointing to v1 = it1[-1].data v2 = it2[-1].data # Updating final answer ans = min(abs(v1 - v2), ans) # Case when v1 < v2 if (v1 < v2): it1 = next(it1) else: it2 = next(it2) # Return ans return ans# Driver codeif __name__ == "__main__": # BST-1 # 5 # / # 3 7 # / / # 2 4 6 8 root2 = node(5) root2.left = node(3) root2.right = node(7) root2.left.left = node(2) root2.left.right = node(4) root2.right.left = node(6) root2.right.right = node(8) # BST-2 # 11 # # 15 # root1 = node(11) root1.right = node(15) print(minDiff(root1, root2))# This code is contributed by mohit kumar 29 |
C#
// C# implementation of the approachusing System;using System.Collections.Generic;class GFG{// Node of Binary treeclass node{ public int data; public node left; public node right; public node(int data) { this.data = data; left = null; right = null; }};// Function to iterate to the// next element of the BSTstatic void next(Stack<node> it){ node curr = it.Peek().right; it.Pop(); while (curr != null) { it.Push(curr); curr = curr.left; }}// Function to find minimum differencestatic int minDiff(node root1, node root2){ // Iterator for two Binary Search Trees Stack<node> it1 = new Stack<node>(); Stack<node> it2 = new Stack<node>(); // Initializing first iterator node curr = root1; while (curr != null) { it1.Push(curr); curr = curr.left; } // Initializing second iterator curr = root2; while (curr != null) { it2.Push(curr); curr = curr.left; } // Variable to store readonly answer int ans = int.MaxValue; // Two pointer technique while (it1.Count > 0 && it2.Count > 0) { // value it1 and it2 are pointing to int v1 = it1.Peek().data; int v2 = it2.Peek().data; // Updating readonly answer ans = Math.Min(Math.Abs(v1 - v2), ans); // Case when v1 < v2 if (v1 < v2) next(it1); else next(it2); } // Return ans return ans;}// Driver codepublic static void Main(String[] args){ // BST-1 /* 5 / 3 7 / / 2 4 6 8 */ node root2 = new node(5); root2.left = new node(3); root2.right = new node(7); root2.left.left = new node(2); root2.left.right = new node(4); root2.right.left = new node(6); root2.right.right = new node(8); // BST-2 /* 11 15 */ node root1 = new node(11); root1.right = new node(15); Console.WriteLine(minDiff(root1, root2));}}// This code is contributed by Rajput-Ji
РЕКОМЕНДУЕМЫЕ СТАТЬИ |