Dados dos BST que contienen n1 y n2 Nodes distintos respectivamente. Dado un valor x . El problema es contar todos los pares de ambos BST cuya suma sea igual a x .
Ejemplos:
Input : BST 1: 5
/ \
3 7
/ \ / \
2 4 6 8
BST 2: 10
/ \
6 15
/ \ / \
3 8 11 18
x = 16
Output : 3
The pairs are:
(5, 11), (6, 10) and (8, 8)
Método 1: Para cada valor de Node a en BST 1, busque el valor (x – a) en BST 2. Si se encuentra el valor, incremente el conteo . Para buscar un valor en BST, consulte esta publicación.
Complejidad de tiempo: O (n1 * h2), aquí n1 es el número de Nodes en el primer BST y h2 es la altura del segundo BST.
Método 2: Atraviese BST 1 desde el valor más pequeño hasta el Node y el más grande. Esto se puede lograr con la ayuda del recorrido iterativo en orden . Atraviese BST 2 desde el Node de mayor valor al más pequeño. Esto se puede lograr con la ayuda del recorrido en orden inverso. Realice estos dos recorridos simultáneamente. Sume el valor del Node correspondiente de ambos BST en una instancia particular de recorridos. Si suma == x, entonces incrementa la cuenta . Si x > sum, muévase al sucesor en orden del Node actual de BST 1, de lo contrario muévase al predecesor en orden del Node actual de BST 2. Realice estas operaciones hasta que se complete cualquiera de los dos recorridos.
Implementación:
C++
// C++ implementation to count pairs from two
// BSTs whose sum is equal to a given value x
#include <bits/stdc++.h>
using namespace std;
// structure of a node of BST
struct Node {
int data;
Node* left, *right;
};
// function to create and return a node of BST
Node* getNode(int data)
{
// allocate space for the node
Node* new_node = (Node*)malloc(sizeof(Node));
// put in the data
new_node->data = data;
new_node->left = new_node->right = NULL;
}
// function to count pairs from two BSTs
// whose sum is equal to a given value x
int countPairs(Node* root1, Node* root2, int x)
{
// if either of the tree is empty
if (root1 == NULL || root2 == NULL)
return 0;
// stack 'st1' used for the inorder
// traversal of BST 1
// stack 'st2' used for the reverse
// inorder traversal of BST 2
stack<Node*> st1, st2;
Node* top1, *top2;
int count = 0;
// the loop will break when either of two
// traversals gets completed
while (1) {
// to find next node in inorder
// traversal of BST 1
while (root1 != NULL) {
st1.push(root1);
root1 = root1->left;
}
// to find next node in reverse
// inorder traversal of BST 2
while (root2 != NULL) {
st2.push(root2);
root2 = root2->right;
}
// if either gets empty then corresponding
// tree traversal is completed
if (st1.empty() || st2.empty())
break;
top1 = st1.top();
top2 = st2.top();
// if the sum of the node's is equal to 'x'
if ((top1->data + top2->data) == x) {
// increment count
count++;
// pop nodes from the respective stacks
st1.pop();
st2.pop();
// insert next possible node in the
// respective stacks
root1 = top1->right;
root2 = top2->left;
}
// move to next possible node in the
// inorder traversal of BST 1
else if ((top1->data + top2->data) < x) {
st1.pop();
root1 = top1->right;
}
// move to next possible node in the
// reverse inorder traversal of BST 2
else {
st2.pop();
root2 = top2->left;
}
}
// required count of pairs
return count;
}
// Driver program to test above
int main()
{
// formation of BST 1
Node* root1 = getNode(5); /* 5 */
root1->left = getNode(3); /* / \ */
root1->right = getNode(7); /* 3 7 */
root1->left->left = getNode(2); /* / \ / \ */
root1->left->right = getNode(4); /* 2 4 6 8 */
root1->right->left = getNode(6);
root1->right->right = getNode(8);
// formation of BST 2
Node* root2 = getNode(10); /* 10 */
root2->left = getNode(6); /* / \ */
root2->right = getNode(15); /* 6 15 */
root2->left->left = getNode(3); /* / \ / \ */
root2->left->right = getNode(8); /* 3 8 11 18 */
root2->right->left = getNode(11);
root2->right->right = getNode(18);
int x = 16;
cout << "Pairs = "
<< countPairs(root1, root2, x);
return 0;
}
Java
// Java implementation to count pairs from two
// BSTs whose sum is equal to a given value x
import java.util.Stack;
public class GFG {
// structure of a node of BST
static class Node {
int data;
Node left, right;
// constructor
public Node(int data) {
this.data = data;
left = null;
right = null;
}
}
static Node root1;
static Node root2;
// function to count pairs from two BSTs
// whose sum is equal to a given value x
static int countPairs(Node root1, Node root2,
int x)
{
// if either of the tree is empty
if (root1 == null || root2 == null)
return 0;
// stack 'st1' used for the inorder
// traversal of BST 1
// stack 'st2' used for the reverse
// inorder traversal of BST 2
//stack<Node*> st1, st2;
Stack<Node> st1 = new Stack<>();
Stack<Node> st2 = new Stack<>();
Node top1, top2;
int count = 0;
// the loop will break when either of two
// traversals gets completed
while (true) {
// to find next node in inorder
// traversal of BST 1
while (root1 != null) {
st1.push(root1);
root1 = root1.left;
}
// to find next node in reverse
// inorder traversal of BST 2
while (root2 != null) {
st2.push(root2);
root2 = root2.right;
}
// if either gets empty then corresponding
// tree traversal is completed
if (st1.empty() || st2.empty())
break;
top1 = st1.peek();
top2 = st2.peek();
// if the sum of the node's is equal to 'x'
if ((top1.data + top2.data) == x) {
// increment count
count++;
// pop nodes from the respective stacks
st1.pop();
st2.pop();
// insert next possible node in the
// respective stacks
root1 = top1.right;
root2 = top2.left;
}
// move to next possible node in the
// inorder traversal of BST 1
else if ((top1.data + top2.data) < x) {
st1.pop();
root1 = top1.right;
}
// move to next possible node in the
// reverse inorder traversal of BST 2
else {
st2.pop();
root2 = top2.left;
}
}
// required count of pairs
return count;
}
// Driver program to test above
public static void main(String args[])
{
// formation of BST 1
root1 = new Node(5); /* 5 */
root1.left = new Node(3); /* / \ */
root1.right = new Node(7); /* 3 7 */
root1.left.left = new Node(2); /* / \ / \ */
root1.left.right = new Node(4); /* 2 4 6 8 */
root1.right.left = new Node(6);
root1.right.right = new Node(8);
// formation of BST 2
root2 = new Node(10); /* 10 */
root2.left = new Node(6); /* / \ */
root2.right = new Node(15); /* 6 15 */
root2.left.left = new Node(3); /* / \ / \ */
root2.left.right = new Node(8); /* 3 8 11 18 */
root2.right.left = new Node(11);
root2.right.right = new Node(18);
int x = 16;
System.out.println("Pairs = "
+ countPairs(root1, root2, x));
}
}
// This code is contributed by Sumit Ghosh
Python3
# Python3 implementation to count pairs
# from two BSTs whose sum is equal to a
# given value x
# Structure of a node of BST
class getNode:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
# Function to count pairs from two BSTs
# whose sum is equal to a given value x
def countPairs(root1, root2, x):
# If either of the tree is empty
if (root1 == None or root2 == None):
return 0
# Stack 'st1' used for the inorder
# traversal of BST 1
# stack 'st2' used for the reverse
# inorder traversal of BST 2
st1 = []
st2 = []
count = 3
# The loop will break when either
# of two traversals gets completed
while (1):
# To find next node in inorder
# traversal of BST 1
while (root1 != None):
st1.append(root1)
root1 = root1.left
# To find next node in reverse
# inorder traversal of BST 2
while (root2 != None):
st2.append(root2)
root2 = root2.right
# If either gets empty then corresponding
# tree traversal is completed
if (len(st1) or len(st2)):
break
top1 = st1[len(st1) - 1]
top2 = st2[len(st2) - 1]
# If the sum of the node's is equal to 'x'
if ((top1.data + top2.data) == x):
# Increment count
count += 1
# Pop nodes from the respective stacks
st1.remove(st1[len(st1) - 1])
st2.remove(st2[len(st2) - 1])
# Insert next possible node in the
# respective stacks
root1 = top1.right
root2 = top2.left
# Move to next possible node in the
# inorder traversal of BST 1
elif ((top1.data + top2.data) < x):
st1.remove(st1[len(st1) - 1])
root1 = top1.right
# Move to next possible node in the
# reverse inorder traversal of BST 2
else:
st2.remove(st2[len(st2) - 1])
root2 = top2.left
# Required count of pairs
return count
# Driver code
if __name__ == '__main__':
# Formation of BST 1
''' 5
/ \
3 7
/ \ / \
2 4 6 8
'''
root1 = getNode(5)
root1.left = getNode(3)
root1.right = getNode(7)
root1.left.left = getNode(2)
root1.left.right = getNode(4)
root1.right.left = getNode(6)
root1.right.right = getNode(8)
# Formation of BST 2
''' 10
/ \
6 15
/ \ / \
3 8 11 18
'''
root2 = getNode(10)
root2.left = getNode(6)
root2.right = getNode(15)
root2.left.left = getNode(3)
root2.left.right = getNode(8)
root2.right.left = getNode(11)
root2.right.right = getNode(18)
x = 16
print("Pairs = ", countPairs(root1, root2, x))
# This code is contributed by bgangwar59
C#
// C# implementation to count pairs from two
// BSTs whose sum is equal to a given value x
using System;
using System.Collections.Generic;
// C# implementation to count pairs from two
// BSTs whose sum is equal to a given value x
public class GFG
{
// structure of a node of BST
public class Node
{
public int data;
public Node left, right;
// constructor
public Node(int data)
{
this.data = data;
left = null;
right = null;
}
}
public static Node root1;
public static Node root2;
// function to count pairs from two BSTs
// whose sum is equal to a given value x
public static int countPairs(Node root1, Node root2, int x)
{
// if either of the tree is empty
if (root1 == null || root2 == null)
{
return 0;
}
// stack 'st1' used for the inorder
// traversal of BST 1
// stack 'st2' used for the reverse
// inorder traversal of BST 2
//stack<Node*> st1, st2;
Stack<Node> st1 = new Stack<Node>();
Stack<Node> st2 = new Stack<Node>();
Node top1, top2;
int count = 0;
// the loop will break when either of two
// traversals gets completed
while (true)
{
// to find next node in inorder
// traversal of BST 1
while (root1 != null)
{
st1.Push(root1);
root1 = root1.left;
}
// to find next node in reverse
// inorder traversal of BST 2
while (root2 != null)
{
st2.Push(root2);
root2 = root2.right;
}
// if either gets empty then corresponding
// tree traversal is completed
if (st1.Count == 0 || st2.Count == 0)
{
break;
}
top1 = st1.Peek();
top2 = st2.Peek();
// if the sum of the node's is equal to 'x'
if ((top1.data + top2.data) == x)
{
// increment count
count++;
// pop nodes from the respective stacks
st1.Pop();
st2.Pop();
// insert next possible node in the
// respective stacks
root1 = top1.right;
root2 = top2.left;
}
// move to next possible node in the
// inorder traversal of BST 1
else if ((top1.data + top2.data) < x)
{
st1.Pop();
root1 = top1.right;
}
// move to next possible node in the
// reverse inorder traversal of BST 2
else
{
st2.Pop();
root2 = top2.left;
}
}
// required count of pairs
return count;
}
// Driver program to test above
public static void Main(string[] args)
{
// formation of BST 1
root1 = new Node(5); // 5
root1.left = new Node(3); // / \
root1.right = new Node(7); // 3 7
root1.left.left = new Node(2); // / \ / \
root1.left.right = new Node(4); // 2 4 6 8
root1.right.left = new Node(6);
root1.right.right = new Node(8);
// formation of BST 2
root2 = new Node(10); // 10
root2.left = new Node(6); // / \
root2.right = new Node(15); // 6 15
root2.left.left = new Node(3); // / \ / \
root2.left.right = new Node(8); // 3 8 11 18
root2.right.left = new Node(11);
root2.right.right = new Node(18);
int x = 16;
Console.WriteLine("Pairs = " + countPairs(root1, root2, x));
}
}
// This code is contributed by Shrikant13
Javascript
<script>
// JavaScript implementation to count pairs
// from two BSTs whose sum is equal to a
// given value x
// Structure of a node of BST
class getNode{
constructor(data){
this.data = data
this.left = null
this.right = null
}
}
// Function to count pairs from two BSTs
// whose sum is equal to a given value x
function countPairs(root1, root2, x){
// If either of the tree is empty
if (root1 == null || root2 == null)
return 0
// Stack 'st1' used for the inorder
// traversal of BST 1
// stack 'st2' used for the reverse
// inorder traversal of BST 2
let st1 = []
let st2 = []
let count = 3
// The loop will break when either
// of two traversals gets completed
while (1){
// To find next node in inorder
// traversal of BST 1
while (root1 != null){
st1.push(root1)
root1 = root1.left
}
// To find next node in reverse
// inorder traversal of BST 2
while (root2 != null){
st2.push(root2)
root2 = root2.right
}
// If either gets empty then corresponding
// tree traversal is completed
if (st1.length || st2.length)
break
top1 = st1[st1.length - 1]
top2 = st2[st2.length - 1]
// If the sum of the node's is equal to 'x'
if ((top1.data + top2.data) == x){
// Increment count
count += 1
// Pop nodes from the respective stacks
st1.pop()
st2.pop()
// Insert next possible node in the
// respective stacks
root1 = top1.right
root2 = top2.left
}
// Move to next possible node in the
// inorder traversal of BST 1
else if ((top1.data + top2.data) < x){
st1.pop()
root1 = top1.right
}
// Move to next possible node in the
// reverse inorder traversal of BST 2
else{
st2.pop()
root2 = top2.left
}
}
// Required count of pairs
return count
}
// Driver code
// Formation of BST 1
// 5
// / \
// 3 7
// / \ / \
// 2 4 6 8
let root1 = new getNode(5)
root1.left = new getNode(3)
root1.right = new getNode(7)
root1.left.left = new getNode(2)
root1.left.right = new getNode(4)
root1.right.left = new getNode(6)
root1.right.right = new getNode(8)
// Formation of BST 2
// 10
// / \
// 6 15
// / \ / \
// 3 8 11 18
let root2 = new getNode(10)
root2.left = new getNode(6)
root2.right = new getNode(15)
root2.left.left = new getNode(3)
root2.left.right = new getNode(8)
root2.right.left = new getNode(11)
root2.right.right = new getNode(18)
let x = 16
document.write("Pairs = ", countPairs(root1, root2, x),"</br>")
// This code is contributed by shinjanpatra
</script>
Producción
Pairs = 3
Complejidad de tiempo: O(n1 + n2)
Espacio auxiliar: O(h1 + h2) Donde h1 es la altura del primer árbol y h2 es la altura del segundo árbol
Método 3:
- Enfoque recursivo para resolver esta pregunta.
- Atraviese el BST1 y para cada Node encuentre la diferencia, es decir (x – root1.data) en BST2 e incremente el conteo.
Implementación:
Java
// Java implementation to count pairs from two
// BSTs whose sum is equal to a given value x
import java.util.Stack;
public class GFG {
// structure of a node of BST
static class Node {
int data;
Node left, right;
// constructor
public Node(int data)
{
this.data = data;
left = null;
right = null;
}
}
static Node root1;
static Node root2;
// function to count pairs from two BSTs
// whose sum is equal to a given value x
public static int pairCount = 0;
public static void traverseTree(Node root1, Node root2,
int sum)
{
if (root1 == null || root2 == null) {
return;
}
traverseTree(root1.left, root2, sum);
traverseTree(root1.right, root2, sum);
int diff = sum - root1.data;
findPairs(root2, diff);
}
private static void findPairs(Node root2, int diff)
{
if (root2 == null) {
return;
}
if (diff > root2.data) {
findPairs(root2.right, diff);
}
else {
findPairs(root2.left, diff);
}
if (root2.data == diff) {
pairCount++;
}
}
public static int countPairs(Node root1, Node root2,
int sum)
{
traverseTree(root1, root2, sum);
return pairCount;
}
// Driver program to test above
public static void main(String args[])
{
// formation of BST 1
root1 = new Node(5); /* 5 */
root1.left = new Node(3); /* / \ */
root1.right = new Node(7); /* 3 7 */
root1.left.left = new Node(2); /* / \ / \ */
root1.left.right = new Node(4); /* 2 4 6 8 */
root1.right.left = new Node(6);
root1.right.right = new Node(8);
// formation of BST 2
root2 = new Node(10); /* 10 */
root2.left = new Node(6); /* / \ */
root2.right = new Node(15); /* 6 15 */
root2.left.left = new Node(3); /* / \ / \ */
root2.left.right
= new Node(8); /* 3 8 11 18 */
root2.right.left = new Node(11);
root2.right.right = new Node(18);
int x = 16;
System.out.println("Pairs = "
+ countPairs(root1, root2, x));
}
}
// This code is contributed by Sujit Panda
Python3
# Python implementation to count pairs from two
# BSTs whose sum is equal to a given value x
# structure of a node of BST
class Node:
# constructor
def __init__(self,data):
self.data = data
self.left = None
self.right = None
root1,root2 = None,None
# def to count pairs from two BSTs
# whose sum is equal to a given value x
pairCount = 0
def traverseTree(root1, root2, sum):
if (root1 == None or root2 == None):
return
traverseTree(root1.left, root2, sum)
traverseTree(root1.right, root2, sum)
diff = sum - root1.data
findPairs(root2, diff)
def findPairs(root2 , diff):
global pairCount
if (root2 == None):
return
if (diff > root2.data) :
findPairs(root2.right, diff)
else :
findPairs(root2.left, diff)
if (root2.data == diff):
pairCount += 1
def countPairs(root1, root2, sum):
global pairCount
traverseTree(root1, root2, sum)
return pairCount
# Driver program to test above
# formation of BST 1
root1 = Node(5)
root1.left = Node(3)
root1.right = Node(7)
root1.left.left = Node(2)
root1.left.right = Node(4)
root1.right.left = Node(6)
root1.right.right = Node(8)
# formation of BST 2
root2 = Node(10)
root2.left = Node(6)
root2.right = Node(15)
root2.left.left = Node(3)
root2.left.right = Node(8)
root2.right.left = Node(11)
root2.right.right = Node(18)
x = 16
print(f"Pairs = {countPairs(root1, root2, x)}")
# This code is contributed by shinjanpatra
C#
// C# implementation to count pairs from two
// BSTs whose sum is equal to a given value x
using System;
using System.Collections.Generic;
public class GFG {
// structure of a node of BST
public class Node {
public int data;
public Node left, right;
// constructor
public Node(int data)
{
this.data = data;
left = null;
right = null;
}
}
static Node root1;
static Node root2;
// function to count pairs from two BSTs
// whose sum is equal to a given value x
public static int pairCount = 0;
public static void traverseTree(Node root1, Node root2,
int sum)
{
if (root1 == null || root2 == null) {
return;
}
traverseTree(root1.left, root2, sum);
traverseTree(root1.right, root2, sum);
int diff = sum - root1.data;
findPairs(root2, diff);
}
private static void findPairs(Node root2, int diff)
{
if (root2 == null) {
return;
}
if (diff > root2.data) {
findPairs(root2.right, diff);
}
else {
findPairs(root2.left, diff);
}
if (root2.data == diff) {
pairCount++;
}
}
public static int countPairs(Node root1, Node root2,
int sum)
{
traverseTree(root1, root2, sum);
return pairCount;
}
// Driver program to test above
public static void Main(String []args)
{
// formation of BST 1
root1 = new Node(5); /* 5 */
root1.left = new Node(3); /* / \ */
root1.right = new Node(7); /* 3 7 */
root1.left.left = new Node(2); /* / \ / \ */
root1.left.right = new Node(4); /* 2 4 6 8 */
root1.right.left = new Node(6);
root1.right.right = new Node(8);
// formation of BST 2
root2 = new Node(10); /* 10 */
root2.left = new Node(6); /* / \ */
root2.right = new Node(15); /* 6 15 */
root2.left.left = new Node(3); /* / \ / \ */
root2.left.right
= new Node(8); /* 3 8 11 18 */
root2.right.left = new Node(11);
root2.right.right = new Node(18);
int x = 16;
Console.WriteLine("Pairs = "
+ countPairs(root1, root2, x));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// javascript implementation to count pairs from two
// BSTs whose sum is equal to a given value x
// structure of a node of BST
class Node {
// constructor
constructor(data)
{
this.data = data;
this.left = null;
this.right = null;
}
}
var root1;
var root2;
// function to count pairs from two BSTs
// whose sum is equal to a given value x
var pairCount = 0;
function traverseTree(root1, root2,
sum)
{
if (root1 == null || root2 == null) {
return;
}
traverseTree(root1.left, root2, sum);
traverseTree(root1.right, root2, sum);
var diff = sum - root1.data;
findPairs(root2, diff);
}
function findPairs(root2 , diff)
{
if (root2 == null) {
return;
}
if (diff > root2.data) {
findPairs(root2.right, diff);
}
else {
findPairs(root2.left, diff);
}
if (root2.data == diff) {
pairCount++;
}
}
function countPairs(root1, root2,
sum)
{
traverseTree(root1, root2, sum);
return pairCount;
}
// Driver program to test above
// formation of BST 1
root1 = new Node(5); /* 5 */
root1.left = new Node(3); /* / \ */
root1.right = new Node(7); /* 3 7 */
root1.left.left = new Node(2); /* / \ / \ */
root1.left.right = new Node(4); /* 2 4 6 8 */
root1.right.left = new Node(6);
root1.right.right = new Node(8);
// formation of BST 2
root2 = new Node(10); /* 10 */
root2.left = new Node(6); /* / \ */
root2.right = new Node(15); /* 6 15 */
root2.left.left = new Node(3); /* / \ / \ */
root2.left.right
= new Node(8); /* 3 8 11 18 */
root2.right.left = new Node(11);
root2.right.right = new Node(18);
var x = 16;
document.write("Pairs = "
+ countPairs(root1, root2, x));
// This code is contributed by Rajput-Ji
</script>
Producción
Pairs = 3
Método 4: Usar BinarySearch Tree Iterator (una forma más general de hacer esto)
Cree dos clases, una como BSTIterator1 y otra como BSTIterator2 . Estas dos clases corresponden a inOrder y reversa inOrder transversal respectivamente.
Cada clase tendrá tres métodos:
- hasNext : devolverá verdadero cuando el recorrido aún no se haya completado
- siguiente : moverá el puntero al siguiente Node
- peek : devolverá el Node actual en el recorrido
Después de crear dos de esas clases, simplemente ejecute el iterador mientras ambos tienen el siguiente Node y encuentre la suma. Si suma == x, incrementa el siguiente puntero de iterador1 e iterador2 y si suma > x, incrementa el siguiente puntero de iterador2; de lo contrario, incrementa el siguiente puntero de iterador1, es decir, cuando suma <x.
Implementación:
Java
import java.util.*;
class Node{
int data;
Node left, right;
public Node(int data){
this.data = data;
this.left = null;
this.right = null;
}
}
// inorder successor iterator
class BSTIterator1{
Stack<Node> s1 = new Stack<>();
Node root1;
boolean hasPeeked = false;
public BSTIterator1(Node root){
this.root1 = root;
}
public boolean hasNext(){
if(!s1.isEmpty() || root1!=null)
return true;
return false;
}
public Node peek(){
if(!hasNext())
return null;
while(root1!=null){
s1.push(root1);
root1 = root1.left;
hasPeeked = true;
}
return s1.peek();
}
public int next(){
if(!hasNext())
return -1;
if(!hasPeeked)
peek();
hasPeeked = false;
root1 = s1.pop();
Node temp = root1;
root1 = root1.right;
return temp.data;
}
}
// inorder predecessor iterator
class BSTIterator2{
Stack<Node> s1 = new Stack<>();
Node root1;
boolean hasPeeked = false;
public BSTIterator2(Node root){
this.root1 = root;
}
public boolean hasNext(){
if(!s1.isEmpty() || root1!=null)
return true;
return false;
}
public Node peek(){
if(!hasNext())
return null;
while(root1!=null){
s1.push(root1);
root1 = root1.right;
hasPeeked = true;
}
return s1.peek();
}
public int next(){
if(!hasNext())
return -1;
if(!hasPeeked)
peek();
hasPeeked = false;
root1 = s1.pop();
Node temp = root1;
root1 = root1.left;
return temp.data;
}
}
class GfG
{
public static int countPairs(Node r1, Node r2, int x)
{
BSTIterator1 it1 = new BSTIterator1(r1);
BSTIterator2 it2 = new BSTIterator2(r2);
int count = 0;
while(it1.hasNext() && it2.hasNext()){
Node n1 = it1.peek();
Node n2 = it2.peek();
int sum = n1.data+n2.data;
if(sum == x){
count++;
it1.next();
it2.next();
}
else if(sum > x){
it2.next();
}else{
it1.next();
}
}
return count;
}
// Driver program to test above
public static void main(String args[])
{
Node root1, root2;
// formation of BST 1
root1 = new Node(5); /* 5 */
root1.left = new Node(3); /* / \ */
root1.right = new Node(7); /* 3 7 */
root1.left.left = new Node(2); /* / \ / \ */
root1.left.right = new Node(4); /* 2 4 6 8 */
root1.right.left = new Node(6);
root1.right.right = new Node(8);
// formation of BST 2
root2 = new Node(10); /* 10 */
root2.left = new Node(6); /* / \ */
root2.right = new Node(15); /* 6 15 */
root2.left.left = new Node(3); /* / \ / \ */
root2.left.right
= new Node(8); /* 3 8 11 18 */
root2.right.left = new Node(11);
root2.right.right = new Node(18);
int x = 16;
System.out.println("Pairs = "
+ countPairs(root1, root2, x));
}
}
Python3
class Node:
data = 0
left = None
right = None
def __init__(self, data):
self.data = data
self.left = None
self.right = None
# inorder successor iterator
class BSTIterator1:
s1 = []
root1 = None
hasPeeked = False
def __init__(self, root):
self.root1 = root
def hasNext(self):
if (not (len(self.s1) == 0) or self.root1 != None):
return True
return False
def peek(self):
if (not self.hasNext()):
return None
while (self.root1 != None):
self.s1.append(self.root1)
self.root1 = self.root1.left
self.hasPeeked = True
return self.s1[-1]
def next(self):
if (not self.hasNext()):
return -1
if (not self.hasPeeked):
self.peek()
self.hasPeeked = False
self.root1 = self.s1.pop()
temp = self.root1
self.root1 = self.root1.right
return temp.data
# inorder predecessor iterator
class BSTIterator2:
s1 = []
root1 = None
hasPeeked = False
def __init__(self, root):
self.root1 = root
def hasNext(self):
if (not (len(self.s1) == 0) or self.root1 != None):
return True
return False
def peek(self):
if (not self.hasNext()):
return None
while (self.root1 != None):
self.s1.append(self.root1)
self.root1 = self.root1.right
self.hasPeeked = True
return self.s1[-1]
def next(self):
if (not self.hasNext()):
return -1
if (not self.hasPeeked):
self.peek()
self.hasPeeked = False
self.root1 = self.s1.pop()
temp = self.root1
self.root1 = self.root1.left
return temp.data
class GfG:
@staticmethod
def countPairs(r1, r2, x):
it1 = BSTIterator1(r1)
it2 = BSTIterator2(r2)
count = 0
while (it1.hasNext() and it2.hasNext()):
n1 = it1.peek()
n2 = it2.peek()
sum = n1.data + n2.data
if (sum == x):
count += 1
it1.next()
it2.next()
elif(sum > x):
it2.next()
else:
it1.next()
return count
# Driver program to test above
@staticmethod
def main(args):
root1 = None
root2 = None
# formation of BST 1
root1 = Node(5)
# 5
root1.left = Node(3)
# / \
root1.right = Node(7)
# 3 7
root1.left.left = Node(2)
# / \ / \
root1.left.right = Node(4)
# 2 4 6 8
root1.right.left = Node(6)
root1.right.right = Node(8)
# formation of BST 2
root2 = Node(10)
# 10
root2.left = Node(6)
# / \
root2.right = Node(15)
# 6 15
root2.left.left = Node(3)
# / \ / \
root2.left.right = Node(8)
# 3 8 11 18
root2.right.left = Node(11)
root2.right.right = Node(18)
x = 16
print("Pairs = " + str(GfG.countPairs(root1, root2, x)))
if __name__ == "__main__":
GfG.main([])
# This code is contributed by mukulsomukesh
C#
using System;
using System.Collections.Generic;
public class Node{
public int data;
public Node left, right;
public Node(int data){
this.data = data;
this.left = null;
this.right = null;
}
}
// inorder successor iterator
public class BSTIterator1{
public Stack<Node> s1 = new Stack<Node>();
public Node root1;
public bool hasPeeked = false;
public BSTIterator1(Node root){
this.root1 = root;
}
public bool hasNext(){
if(s1.Count != 0 || root1 != null)
return true;
return false;
}
public Node peek(){
if(!hasNext())
return null;
while(root1 != null){
s1.Push(root1);
root1 = root1.left;
hasPeeked = true;
}
return s1.Peek();
}
public int next(){
if(!hasNext())
return -1;
if(!hasPeeked)
peek();
hasPeeked = false;
root1 = s1.Pop();
Node temp = root1;
root1 = root1.right;
return temp.data;
}
}
// inorder predecessor iterator
public class BSTIterator2{
public Stack<Node> s1 = new Stack<Node>();
public Node root1;
public bool hasPeeked = false;
public BSTIterator2(Node root){
this.root1 = root;
}
public bool hasNext(){
if(s1.Count != 0 || root1 != null)
return true;
return false;
}
public Node peek(){
if(!hasNext())
return null;
while(root1 != null){
s1.Push(root1);
root1 = root1.right;
hasPeeked = true;
}
return s1.Peek();
}
public int next(){
if(!hasNext())
return -1;
if(!hasPeeked)
peek();
hasPeeked = false;
root1 = s1.Pop();
Node temp = root1;
root1 = root1.left;
return temp.data;
}
}
public class GfG
{
public static int countPairs(Node r1, Node r2, int x)
{
BSTIterator1 it1 = new BSTIterator1(r1);
BSTIterator2 it2 = new BSTIterator2(r2);
int count = 0;
while(it1.hasNext() && it2.hasNext()){
Node n1 = it1.peek();
Node n2 = it2.peek();
int sum = n1.data+n2.data;
if(sum == x){
count++;
it1.next();
it2.next();
}
else if(sum > x){
it2.next();
}else{
it1.next();
}
}
return count;
}
// Driver program to test above
public static void Main(String []args)
{
Node root1, root2;
// formation of BST 1
root1 = new Node(5); /* 5 */
root1.left = new Node(3); /* / \ */
root1.right = new Node(7); /* 3 7 */
root1.left.left = new Node(2); /* / \ / \ */
root1.left.right = new Node(4); /* 2 4 6 8 */
root1.right.left = new Node(6);
root1.right.right = new Node(8);
// formation of BST 2
root2 = new Node(10); /* 10 */
root2.left = new Node(6); /* / \ */
root2.right = new Node(15); /* 6 15 */
root2.left.left = new Node(3); /* / \ / \ */
root2.left.right
= new Node(8); /* 3 8 11 18 */
root2.right.left = new Node(11);
root2.right.right = new Node(18);
int x = 16;
Console.WriteLine("Pairs = "
+ countPairs(root1, root2, x));
}
}
// This code is contributed by Rajput-Ji
Producción
Pairs = 3
Complejidad del Tiempo: O(n1 + n2)
Espacio auxiliar: O(h1 + h2) Donde h1 es la altura del primer árbol y h2 es la altura del segundo árbol
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