Dados dos árboles de búsqueda binarios (BST) y una suma dada. La tarea es encontrar pares con una suma dada de modo que los elementos de cada par deban estar en diferentes BST.
Ejemplos:
Input : sum = 10
8 5
/ \ / \
3 10 2 18
/ \ \ / \
1 6 14 1 3
/ \ / \
5 7 13 4
Output : (5,5), (6,4), (7,3), (8,2)
In above pairs first element lies in first
BST and second element lies in second BST
Una solución simple para este problema es almacenar el recorrido en orden de un árbol en una array auxiliar, luego seleccionar los elementos uno por uno de la array y encontrar su par en otro árbol para la suma dada. La complejidad del tiempo para este enfoque será O(n 2 ) si el total de Nodes en ambos árboles es igual.
Una solución eficiente para esta solución es almacenar recorridos en orden de ambos BST en dos arrays auxiliares diferentes , vect1[] y vect2[]. Ahora seguimos el método 1 de este artículo. Dado que el recorrido Inorder de BST siempre da una secuencia ordenada, no necesitamos ordenar nuestras arrays.
- Tome el iterador a la izquierda y apúntelo a la esquina izquierda vect1[].
- Tome el iterador a la derecha y apúntelo a la esquina derecha vect2[].
- Ahora, si vect11[izquierda] + vect2[derecha] <suma , mueva el iterador izquierdo en vect1[] en dirección hacia adelante, es decir; izquierda++ .
- Ahora, si vect1[izquierda] + vect2[derecha] > sum , mueva el iterador derecho en vect[] hacia atrás, es decir; cierto– .
A continuación se muestra la implementación de la idea anterior.
C++
// C++ program to find pairs with given sum such
// that one element of pair exists in one BST and
// other in other BST.
#include<bits/stdc++.h>
using namespace std;
// A binary Tree node
struct Node
{
int data;
struct Node *left, *right;
};
// A utility function to create a new BST node
// with key as given num
struct Node* newNode(int num)
{
struct Node* temp = new Node;
temp->data = num;
temp->left = temp->right = NULL;
return temp;
}
// A utility function to insert a given key to BST
Node* insert(Node* root, int key)
{
if (root == NULL)
return newNode(key);
if (root->data > key)
root->left = insert(root->left, key);
else
root->right = insert(root->right, key);
return root;
}
// store storeInorder traversal in auxiliary array
void storeInorder(Node *ptr, vector<int> &vect)
{
if (ptr==NULL)
return;
storeInorder(ptr->left, vect);
vect.push_back(ptr->data);
storeInorder(ptr->right, vect);
}
// Function to find pair for given sum in different bst
// vect1[] --> stores storeInorder traversal of first bst
// vect2[] --> stores storeInorder traversal of second bst
void pairSumUtil(vector<int> &vect1, vector<int> &vect2,
int sum)
{
// Initialize two indexes to two different corners
// of two vectors.
int left = 0;
int right = vect2.size() - 1;
// find pair by moving two corners.
while (left < vect1.size() && right >= 0)
{
// If we found a pair
if (vect1[left] + vect2[right] == sum)
{
cout << "(" << vect1[left] << ", "
<< vect2[right] << "), ";
left++;
right--;
}
// If sum is more, move to higher value in
// first vector.
else if (vect1[left] + vect2[right] < sum)
left++;
// If sum is less, move to lower value in
// second vector.
else
right--;
}
}
// Prints all pairs with given "sum" such that one
// element of pair is in tree with root1 and other
// node is in tree with root2.
void pairSum(Node *root1, Node *root2, int sum)
{
// Store inorder traversals of two BSTs in two
// vectors.
vector<int> vect1, vect2;
storeInorder(root1, vect1);
storeInorder(root2, vect2);
// Now the problem reduces to finding a pair
// with given sum such that one element is in
// vect1 and other is in vect2.
pairSumUtil(vect1, vect2, sum);
}
// Driver program to run the case
int main()
{
// first BST
struct Node* root1 = NULL;
root1 = insert(root1, 8);
root1 = insert(root1, 10);
root1 = insert(root1, 3);
root1 = insert(root1, 6);
root1 = insert(root1, 1);
root1 = insert(root1, 5);
root1 = insert(root1, 7);
root1 = insert(root1, 14);
root1 = insert(root1, 13);
// second BST
struct Node* root2 = NULL;
root2 = insert(root2, 5);
root2 = insert(root2, 18);
root2 = insert(root2, 2);
root2 = insert(root2, 1);
root2 = insert(root2, 3);
root2 = insert(root2, 4);
int sum = 10;
pairSum(root1, root2, sum);
return 0;
}
Java
// Java program to find pairs with given sum such
// that one element of pair exists in one BST and
// other in other BST.
import java.util.*;
class solution
{
// A binary Tree node
static class Node
{
int data;
Node left, right;
};
// A utility function to create a new BST node
// with key as given num
static Node newNode(int num)
{
Node temp = new Node();
temp.data = num;
temp.left = temp.right = null;
return temp;
}
// A utility function to insert a given key to BST
static Node insert(Node root, int key)
{
if (root == null)
return newNode(key);
if (root.data > key)
root.left = insert(root.left, key);
else
root.right = insert(root.right, key);
return root;
}
// store storeInorder traversal in auxiliary array
static void storeInorder(Node ptr, Vector<Integer> vect)
{
if (ptr==null)
return;
storeInorder(ptr.left, vect);
vect.add(ptr.data);
storeInorder(ptr.right, vect);
}
// Function to find pair for given sum in different bst
// vect1.get() -. stores storeInorder traversal of first bst
// vect2.get() -. stores storeInorder traversal of second bst
static void pairSumUtil(Vector<Integer> vect1, Vector<Integer> vect2,
int sum)
{
// Initialize two indexes to two different corners
// of two Vectors.
int left = 0;
int right = vect2.size() - 1;
// find pair by moving two corners.
while (left < vect1.size() && right >= 0)
{
// If we found a pair
if (vect1.get(left) + vect2.get(right) == sum)
{
System.out.print( "(" +vect1.get(left) + ", "+ vect2.get(right) + "), ");
left++;
right--;
}
// If sum is more, move to higher value in
// first Vector.
else if (vect1.get(left) + vect2.get(right) < sum)
left++;
// If sum is less, move to lower value in
// second Vector.
else
right--;
}
}
// Prints all pairs with given "sum" such that one
// element of pair is in tree with root1 and other
// node is in tree with root2.
static void pairSum(Node root1, Node root2, int sum)
{
// Store inorder traversals of two BSTs in two
// Vectors.
Vector<Integer> vect1= new Vector<Integer>(), vect2= new Vector<Integer>();
storeInorder(root1, vect1);
storeInorder(root2, vect2);
// Now the problem reduces to finding a pair
// with given sum such that one element is in
// vect1 and other is in vect2.
pairSumUtil(vect1, vect2, sum);
}
// Driver program to run the case
public static void main(String args[])
{
// first BST
Node root1 = null;
root1 = insert(root1, 8);
root1 = insert(root1, 10);
root1 = insert(root1, 3);
root1 = insert(root1, 6);
root1 = insert(root1, 1);
root1 = insert(root1, 5);
root1 = insert(root1, 7);
root1 = insert(root1, 14);
root1 = insert(root1, 13);
// second BST
Node root2 = null;
root2 = insert(root2, 5);
root2 = insert(root2, 18);
root2 = insert(root2, 2);
root2 = insert(root2, 1);
root2 = insert(root2, 3);
root2 = insert(root2, 4);
int sum = 10;
pairSum(root1, root2, sum);
}
}
//contributed by Arnab Kundu
Python3
# Python3 program to find pairs with given
# sum such that one element of pair exists
# in one BST and other in other BST.
# A utility function to create a new
# BST node with key as given num
class newNode:
# Constructor to create a new node
def __init__(self, data):
self.data = data
self.left = None
self.right = None
# A utility function to insert a
# given key to BST
def insert(root, key):
if root == None:
return newNode(key)
if root.data > key:
root.left = insert(root.left, key)
else:
root.right = insert(root.right, key)
return root
# store storeInorder traversal in
# auxiliary array
def storeInorder(ptr, vect):
if ptr == None:
return
storeInorder(ptr.left, vect)
vect.append(ptr.data)
storeInorder(ptr.right, vect)
# Function to find pair for given
# sum in different bst
# vect1[] --> stores storeInorder traversal
# of first bst
# vect2[] --> stores storeInorder traversal
# of second bst
def pairSumUtil(vect1, vect2, Sum):
# Initialize two indexes to two
# different corners of two lists.
left = 0
right = len(vect2) - 1
# find pair by moving two corners.
while left < len(vect1) and right >= 0:
# If we found a pair
if vect1[left] + vect2[right] == Sum:
print("(", vect1[left], ",",
vect2[right], "),", end = " ")
left += 1
right -= 1
# If sum is more, move to higher
# value in first lists.
else if vect1[left] + vect2[right] < Sum:
left += 1
# If sum is less, move to lower
# value in second lists.
else:
right -= 1
# Prints all pairs with given "sum" such that one
# element of pair is in tree with root1 and other
# node is in tree with root2.
def pairSum(root1, root2, Sum):
# Store inorder traversals of
# two BSTs in two lists.
vect1 = []
vect2 = []
storeInorder(root1, vect1)
storeInorder(root2, vect2)
# Now the problem reduces to finding a
# pair with given sum such that one
# element is in vect1 and other is in vect2.
pairSumUtil(vect1, vect2, Sum)
# Driver Code
if __name__ == '__main__':
# first BST
root1 = None
root1 = insert(root1, 8)
root1 = insert(root1, 10)
root1 = insert(root1, 3)
root1 = insert(root1, 6)
root1 = insert(root1, 1)
root1 = insert(root1, 5)
root1 = insert(root1, 7)
root1 = insert(root1, 14)
root1 = insert(root1, 13)
# second BST
root2 = None
root2 = insert(root2, 5)
root2 = insert(root2, 18)
root2 = insert(root2, 2)
root2 = insert(root2, 1)
root2 = insert(root2, 3)
root2 = insert(root2, 4)
Sum = 10
pairSum(root1, root2, Sum)
# This code is contributed by PranchalK
C#
using System;
using System.Collections.Generic;
// C# program to find pairs with given sum such
// that one element of pair exists in one BST and
// other in other BST.
public class solution
{
// A binary Tree node
public class Node
{
public int data;
public Node left, right;
}
// A utility function to create a new BST node
// with key as given num
public static Node newNode(int num)
{
Node temp = new Node();
temp.data = num;
temp.left = temp.right = null;
return temp;
}
// A utility function to insert a given key to BST
public static Node insert(Node root, int key)
{
if (root == null)
{
return newNode(key);
}
if (root.data > key)
{
root.left = insert(root.left, key);
}
else
{
root.right = insert(root.right, key);
}
return root;
}
// store storeInorder traversal in auxiliary array
public static void storeInorder(Node ptr, List<int> vect)
{
if (ptr == null)
{
return;
}
storeInorder(ptr.left, vect);
vect.Add(ptr.data);
storeInorder(ptr.right, vect);
}
// Function to find pair for given sum in different bst
// vect1.get() -. stores storeInorder traversal of first bst
// vect2.get() -. stores storeInorder traversal of second bst
public static void pairSumUtil(List<int> vect1, List<int> vect2, int sum)
{
// Initialize two indexes to two different corners
// of two Vectors.
int left = 0;
int right = vect2.Count - 1;
// find pair by moving two corners.
while (left < vect1.Count && right >= 0)
{
// If we found a pair
if (vect1[left] + vect2[right] == sum)
{
Console.Write("(" + vect1[left] + ", " + vect2[right] + "), ");
left++;
right--;
}
// If sum is more, move to higher value in
// first Vector.
else if (vect1[left] + vect2[right] < sum)
{
left++;
}
// If sum is less, move to lower value in
// second Vector.
else
{
right--;
}
}
}
// Prints all pairs with given "sum" such that one
// element of pair is in tree with root1 and other
// node is in tree with root2.
public static void pairSum(Node root1, Node root2, int sum)
{
// Store inorder traversals of two BSTs in two
// Vectors.
List<int> vect1 = new List<int>(), vect2 = new List<int>();
storeInorder(root1, vect1);
storeInorder(root2, vect2);
// Now the problem reduces to finding a pair
// with given sum such that one element is in
// vect1 and other is in vect2.
pairSumUtil(vect1, vect2, sum);
}
// Driver program to run the case
public static void Main(string[] args)
{
// first BST
Node root1 = null;
root1 = insert(root1, 8);
root1 = insert(root1, 10);
root1 = insert(root1, 3);
root1 = insert(root1, 6);
root1 = insert(root1, 1);
root1 = insert(root1, 5);
root1 = insert(root1, 7);
root1 = insert(root1, 14);
root1 = insert(root1, 13);
// second BST
Node root2 = null;
root2 = insert(root2, 5);
root2 = insert(root2, 18);
root2 = insert(root2, 2);
root2 = insert(root2, 1);
root2 = insert(root2, 3);
root2 = insert(root2, 4);
int sum = 10;
pairSum(root1, root2, sum);
}
}
// This code is contributed by Shrikant13
Javascript
<script>
// JavaScript program to find pairs with given sum such
// that one element of pair exists in one BST and
// other in other BST.
// A binary Tree node
class Node
{
constructor()
{
this.data = 0;
this.left = null;
this.right = null;
}
}
// A utility function to create a new BST node
// with key as given num
function newNode(num)
{
var temp = new Node();
temp.data = num;
temp.left = temp.right = null;
return temp;
}
// A utility function to insert a given key to BST
function insert(root, key)
{
if (root == null)
{
return newNode(key);
}
if (root.data > key)
{
root.left = insert(root.left, key);
}
else
{
root.right = insert(root.right, key);
}
return root;
}
// store storeInorder traversal in auxiliary array
function storeInorder(ptr, vect)
{
if (ptr == null)
{
return;
}
storeInorder(ptr.left, vect);
vect.push(ptr.data);
storeInorder(ptr.right, vect);
}
// Function to find pair for given sum in different bst
// vect1.get() -. stores storeInorder traversal of first bst
// vect2.get() -. stores storeInorder traversal of second bst
function pairSumUtil(vect1, vect2, sum)
{
// Initialize two indexes to two different corners
// of two Vectors.
var left = 0;
var right = vect2.length - 1;
// find pair by moving two corners.
while (left < vect1.length && right >= 0)
{
// If we found a pair
if (vect1[left] + vect2[right] == sum)
{
document.write("(" + vect1[left] + ", " +
vect2[right] + "), ");
left++;
right--;
}
// If sum is more, move to higher value in
// first Vector.
else if (vect1[left] + vect2[right] < sum)
{
left++;
}
// If sum is less, move to lower value in
// second Vector.
else
{
right--;
}
}
}
// Prints all pairs with given "sum" such that one
// element of pair is in tree with root1 and other
// node is in tree with root2.
function pairSum(root1, root2, sum)
{
// Store inorder traversals of two BSTs in two
// Vectors.
var vect1 = [], vect2 = [];
storeInorder(root1, vect1);
storeInorder(root2, vect2);
// Now the problem reduces to finding a pair
// with given sum such that one element is in
// vect1 and other is in vect2.
pairSumUtil(vect1, vect2, sum);
}
// Driver program to run the case
// first BST
var root1 = null;
root1 = insert(root1, 8);
root1 = insert(root1, 10);
root1 = insert(root1, 3);
root1 = insert(root1, 6);
root1 = insert(root1, 1);
root1 = insert(root1, 5);
root1 = insert(root1, 7);
root1 = insert(root1, 14);
root1 = insert(root1, 13);
// second BST
var root2 = null;
root2 = insert(root2, 5);
root2 = insert(root2, 18);
root2 = insert(root2, 2);
root2 = insert(root2, 1);
root2 = insert(root2, 3);
root2 = insert(root2, 4);
var sum = 10;
pairSum(root1, root2, sum);
</script>
Producción
(5, 5), (6, 4), (7, 3), (8, 2),
Complejidad temporal : O(n)
Espacio auxiliar : O(n)
Tenemos otro enfoque de espacio optimizado para resolver este problema. La idea es convertir bst en una lista doblemente enlazada y aplicar el método anterior para una lista doblemente enlazada. Consulte este artículo.
Complejidad temporal : O(n)
Espacio auxiliar : O(1)
Este artículo es una contribución de Shashank Mishra (Gullu) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA