Dados dos árboles de búsqueda binarios y un entero X , la tarea es encontrar un par de Nodes, uno perteneciente al primer BST y el segundo perteneciente al otro tal que su suma sea igual a X . Si existe tal par, escriba Sí , de lo contrario , escriba No.
Ejemplos:
Input: X = 100
BST 1:
5
/ \
3 7
/ \ / \
2 4 6 8
BST 2:
11
\
13
Output: No
There is no such pair with given value.
Input: X = 16
BST 1:
5
/ \
3 7
/ \ / \
2 4 6 8
BST 2:
11
\
13
Output: Yes
5 + 11 = 16
Enfoque: Resolveremos este problema utilizando el enfoque de dos punteros.
Crearemos un iterador hacia adelante en el primer BST y hacia atrás en el segundo. Por lo tanto, mantendremos un iterador hacia adelante y hacia atrás que iterará los BST en el orden de recorrido en orden y en orden inverso, respectivamente.
- Cree un iterador hacia adelante y hacia atrás para el primer y segundo BST respectivamente. Digamos que el valor de los Nodes a los que apuntan es v1 y v2.
- Ahora en cada paso,
- Si v1 + v2 = X, encontramos un par.
- Si v1 + v2 es menor o igual que x, haremos que el iterador hacia adelante apunte al siguiente elemento.
- Si v1 + v2 es mayor que x, haremos que el iterador hacia atrás apunte al elemento anterior.
- Continuaremos con lo anterior mientras ambos iteradores apuntan a un Node válido.
A continuación se muestra la implementación del enfoque anterior:
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 that returns true if a pair
// with given sum exists in the given BSTs
bool existsPair(node* root1, node* root2, int x)
{
// Stack to store nodes for forward and backward
// iterator
stack<node *> it1, it2;
// Initializing forward iterator
node* c = root1;
while (c != NULL)
it1.push(c), c = c->left;
// Initializing backward iterator
c = root2;
while (c != NULL)
it2.push(c), c = c->right;
// Two pointer technique
while (it1.size() and it2.size()) {
// To store the value of the nodes
// current iterators are pointing to
int v1 = it1.top()->data, v2 = it2.top()->data;
// If found a valid pair
if (v1 + v2 == x)
return true;
// Moving forward iterator
if (v1 + v2 < x) {
c = it1.top()->right;
it1.pop();
while (c != NULL)
it1.push(c), c = c->left;
}
// Moving backward iterator
else {
c = it2.top()->left;
it2.pop();
while (c != NULL)
it2.push(c), c = c->right;
}
}
// If no such pair found
return false;
}
// Driver code
int main()
{
// First BST
node* root1 = new node(11);
root1->right = new node(15);
// Second BST
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);
int x = 23;
if (existsPair(root1, root2, x))
cout << "Yes";
else
cout << "No";
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;
}
};
// Function that returns true if a pair
// with given sum exists in the given BSTs
static boolean existsPair(node root1, node root2, int x)
{
// Stack to store nodes for forward and backward
// iterator
Stack<node> it1 = new Stack(), it2 = new Stack();
// Initializing forward iterator
node c = root1;
while (c != null)
{
it1.push(c);
c = c.left;
}
// Initializing backward iterator
c = root2;
while (c != null)
{
it2.push(c);
c = c.right;
}
// Two pointer technique
while (it1.size() > 0 && it2.size() > 0)
{
// To store the value of the nodes
// current iterators are pointing to
int v1 = it1.peek().data, v2 = it2.peek().data;
// If found a valid pair
if (v1 + v2 == x)
return true;
// Moving forward iterator
if (v1 + v2 < x)
{
c = it1.peek().right;
it1.pop();
while (c != null)
{
it1.push(c); c = c.left;
}
}
// Moving backward iterator
else
{
c = it2.peek().left;
it2.pop();
while (c != null)
{
it2.push(c); c = c.right;
}
}
}
// If no such pair found
return false;
}
// Driver code
public static void main(String[] args)
{
// First BST
node root1 = new node(11);
root1.right = new node(15);
// Second BST
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);
int x = 23;
if (existsPair(root1, root2, x))
System.out.println("Yes");
else
System.out.println("No");
}
}
// This code is contributed by Princi Singh
Python3
# Python3 implementation of the approach
# Node of the binary tree
class node:
def __init__ (self, key):
self.data = key
self.left = None
self.right = None
# Function that returns true if a pair
# with given sum exists in the given BSTs
def existsPair(root1, root2, x):
# Stack to store nodes for forward
# and backward iterator
it1, it2 = [], []
# Initializing forward iterator
c = root1
while (c != None):
it1.append(c)
c = c.left
# Initializing backward iterator
c = root2
while (c != None):
it2.append(c)
c = c.right
# Two pointer technique
while (len(it1) > 0 and len(it2) > 0):
# To store the value of the nodes
# current iterators are pointing to
v1 = it1[-1].data
v2 = it2[-1].data
# If found a valid pair
if (v1 + v2 == x):
return True
# Moving forward iterator
if (v1 + v2 < x):
c = it1[-1].right
del it1[-1]
while (c != None):
it1.append(c)
c = c.left
# Moving backward iterator
else:
c = it2[-1].left
del it2[-1]
while (c != None):
it2.append(c)
c = c.right
# If no such pair found
return False
# Driver code
if __name__ == '__main__':
# First BST
root1 = node(11)
root1.right = node(15)
# Second BST
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)
x = 23
if (existsPair(root1, root2, x)):
print("Yes")
else:
print("No")
# This code is contributed by mohit kumar 29
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
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;
}
};
// Function that returns true if a pair
// with given sum exists in the given BSTs
static bool existsPair(node root1, node root2, int x)
{
// Stack to store nodes for forward and backward
// iterator
Stack<node> it1 = new Stack<node>(), it2 = new Stack<node>();
// Initializing forward iterator
node c = root1;
while (c != null)
{
it1.Push(c);
c = c.left;
}
// Initializing backward iterator
c = root2;
while (c != null)
{
it2.Push(c);
c = c.right;
}
// Two pointer technique
while (it1.Count > 0 && it2.Count > 0)
{
// To store the value of the nodes
// current iterators are pointing to
int v1 = it1.Peek().data, v2 = it2.Peek().data;
// If found a valid pair
if (v1 + v2 == x)
return true;
// Moving forward iterator
if (v1 + v2 < x)
{
c = it1.Peek().right;
it1.Pop();
while (c != null)
{
it1.Push(c); c = c.left;
}
}
// Moving backward iterator
else
{
c = it2.Peek().left;
it2.Pop();
while (c != null)
{
it2.Push(c); c = c.right;
}
}
}
// If no such pair found
return false;
}
// Driver code
public static void Main(String[] args)
{
// First BST
node root1 = new node(11);
root1.right = new node(15);
// Second BST
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);
int x = 23;
if (existsPair(root1, root2, x))
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript implementation of the approach
// Node of the binary tree
class node
{
constructor(data)
{
this.data = data;
this.left = null;
this.right = null;
}
}
// Function that returns true if a pair
// with given sum exists in the given BSTs
function existsPair(root1,root2,x)
{
// Stack to store nodes for forward and backward
// iterator
let it1 =[], it2 = [];
// Initializing forward iterator
let c = root1;
while (c != null)
{
it1.push(c);
c = c.left;
}
// Initializing backward iterator
c = root2;
while (c != null)
{
it2.push(c);
c = c.right;
}
// Two pointer technique
while (it1.length > 0 && it2.length > 0)
{
// To store the value of the nodes
// current iterators are pointing to
let v1 = it1[it1.length-1].data, v2 = it2[it2.length-1].data;
// If found a valid pair
if (v1 + v2 == x)
return true;
// Moving forward iterator
if (v1 + v2 < x)
{
c = it1[it1.length-1].right;
it1.pop();
while (c != null)
{
it1.push(c); c = c.left;
}
}
// Moving backward iterator
else
{
c = it2[it2.length-1].left;
it2.pop();
while (c != null)
{
it2.push(c); c = c.right;
}
}
}
// If no such pair found
return false;
}
// Driver code
// First BST
let root1 = new node(11);
root1.right = new node(15);
// Second BST
let 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);
let x = 23;
if (existsPair(root1, root2, x))
document.write("Yes");
else
document.write("No");
// This code is contributed by patel2127
</script>
Producción:
Yes
Complejidad temporal: O(N)
Espacio auxiliar : O(N)
Publicación traducida automáticamente
Artículo escrito por DivyanshuShekhar1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA