Dado un árbol de búsqueda binario y un número X . La tarea es encontrar el número de pares distintos de Nodes distintos en BST con una suma igual a X . No hay dos Nodes que tengan los mismos valores.
Ejemplos:
Input : X = 5
5
/ \
3 7
/ \ / \
2 4 6 8
Output : 1
{2, 3} is the only possible pair.
Thus, the answer is equal to 1.
Input : X = 6
1
\
2
\
3
\
4
\
5
Output : 2
Possible pairs are {{1, 5}, {2, 4}}.
Enfoque ingenuo : la idea es codificar todos los elementos de BST o convertir el BST en una array ordenada. Después de eso, encuentre el número de pares usando el algoritmo dado aquí .
Complejidad temporal: O(N).
Complejidad espacial: O(N).
Enfoque de espacio optimizado: la idea es utilizar la técnica de dos punteros en BST. Mantenga iteradores hacia adelante y hacia atrás que iteren el BST en el orden de recorrido en orden y en orden inverso, respectivamente.
- Cree iteradores hacia adelante y hacia atrás para BST. Digamos que el valor de los Nodes a los que apuntan es igual a v 1 y v 2 respectivamente.
- Ahora en cada paso,
- Si v 1 + v 2 = X, se encuentra el par, entonces aumente la cuenta en 1.
- Si v 1 + v 2 es menor o igual que x, haremos que el iterador hacia adelante apunte al siguiente elemento.
- Si v 1 + v 2 es mayor que x, haremos que el iterador hacia atrás apunte al elemento anterior.
- Repita los pasos anteriores hasta que ambos iteradores no apunten al mismo Node.
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 Binary tree
struct node {
int data;
node* left;
node* right;
node(int data)
{
this->data = data;
left = NULL;
right = NULL;
}
};
// Function to find a pair
int cntPairs(node* root, int x)
{
// Stack to store nodes for
// forward and backward iterator
stack<node *> it1, it2;
// Initializing forward iterator
node* c = root;
while (c != NULL)
it1.push(c), c = c->left;
// Initializing backward iterator
c = root;
while (c != NULL)
it2.push(c), c = c->right;
// Variable to store final answer
int ans = 0;
// two pointer technique
while (it1.top() != it2.top()) {
// Variables to store the
// value of the nodes current
// iterators are pointing to.
int v1 = it1.top()->data;
int v2 = it2.top()->data;
// If we find a pair
// then count is increased by 1
if (v1 + v2 == x)
ans++;
// 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;
}
}
// Returning final answer
return ans;
}
// Driver code
int main()
{
/* 5
/ \
3 7
/ \ / \
2 4 6 8 */
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);
int x = 10;
cout << cntPairs(root, x);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
// Node of Binary tree
static class node
{
int data;
node left;
node right;
node(int data)
{
this.data = data;
left = null;
right = null;
}
};
// Function to find a pair
static int cntPairs(node root, int x)
{
// Stack to store nodes for
// forward and backward iterator
Stack<node > it1 = new Stack<>();
Stack<node > it2 = new Stack<>();
// Initializing forward iterator
node c = root;
while (c != null)
{
it1.push(c);
c = c.left;
}
// Initializing backward iterator
c = root;
while (c != null)
{
it2.push(c);
c = c.right;
}
// Variable to store final answer
int ans = 0;
// two pointer technique
while (it1.peek() != it2.peek())
{
// Variables to store the
// value of the nodes current
// iterators are pointing to.
int v1 = it1.peek().data;
int v2 = it2.peek().data;
// If we find a pair
// then count is increased by 1
if (v1 + v2 == x)
ans++;
// 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;
}
}
}
// Returning final answer
return ans;
}
// Driver code
public static void main(String[] args)
{
/* 5
/ \
3 7
/ \ / \
2 4 6 8 */
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);
int x = 10;
System.out.print(cntPairs(root, x));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python implementation of above algorithm # Utility class to create a node class node: def __init__(self, key): self.data = key self.left = self.right = None # Function to find a pair def cntPairs( root, x): # Stack to store nodes for # forward and backward iterator it1 = [] it2 = [] # Initializing forward iterator c = root while (c != None): it1.append(c) c = c.left # Initializing backward iterator c = root while (c != None): it2.append(c) c = c.right # Variable to store final answer ans = 0 # two pointer technique while (it1[-1] != it2[-1]) : # Variables to store the # value of the nodes current # iterators are pointing to. v1 = it1[-1].data v2 = it2[-1].data # If we find a pair # then count is increased by 1 if (v1 + v2 == x): ans=ans+1 # Moving forward iterator if (v1 + v2 <= x) : c = it1[-1].right it1.pop() while (c != None): it1.append(c) c = c.left # Moving backward iterator else : c = it2[-1].left it2.pop() while (c != None): it2.append(c) c = c.right # Returning final answer return ans # Driver code # 5 # / \ # 3 7 # / \ / \ # 2 4 6 8 root = node(5) root.left = node(3) root.right = node(7) root.left.left = node(2) root.left.right = node(4) root.right.left = node(6) root.right.right = node(8) x = 10 print(cntPairs(root, x)) # This code is contributed by Arnab Kundu
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
class GFG
{
// Node of 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 to find a pair
static int cntPairs(node root, int x)
{
// Stack to store nodes for
// forward and backward iterator
Stack<node > it1 = new Stack<node>();
Stack<node > it2 = new Stack<node>();
// Initializing forward iterator
node c = root;
while (c != null)
{
it1.Push(c);
c = c.left;
}
// Initializing backward iterator
c = root;
while (c != null)
{
it2.Push(c);
c = c.right;
}
// Variable to store readonly answer
int ans = 0;
// two pointer technique
while (it1.Peek() != it2.Peek())
{
// Variables to store the
// value of the nodes current
// iterators are pointing to.
int v1 = it1.Peek().data;
int v2 = it2.Peek().data;
// If we find a pair
// then count is increased by 1
if (v1 + v2 == x)
ans++;
// 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;
}
}
}
// Returning readonly answer
return ans;
}
// Driver code
public static void Main(String[] args)
{
/* 5
/ \
3 7
/ \ / \
2 4 6 8 */
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);
int x = 10;
Console.Write(cntPairs(root, x));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript implementation of the approach
// Node of Binary tree
class node
{
constructor(data)
{
this.data = data;
this.left = null;
this.right = null;
}
};
// Function to find a pair
function cntPairs(root, x)
{
// Stack to store nodes for
// forward and backward iterator
var it1 = [];
var it2 = [];
// Initializing forward iterator
var c = root;
while (c != null)
{
it1.push(c);
c = c.left;
}
// Initializing backward iterator
c = root;
while (c != null)
{
it2.push(c);
c = c.right;
}
// Variable to store readonly answer
var ans = 0;
// two pointer technique
while (it1[it1.length - 1] != it2[it2.length - 1])
{
// Variables to store the
// value of the nodes current
// iterators are pointing to.
var v1 = it1[it1.length - 1].data;
var v2 = it2[it2.length - 1].data;
// If we find a pair
// then count is increased by 1
if (v1 + v2 == x)
ans++;
// 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;
}
}
}
// Returning readonly answer
return ans;
}
// Driver code
/* 5
/ \
3 7
/ \ / \
2 4 6 8 */
var 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);
var x = 10;
document.write(cntPairs(root, x));
// This code is contributed by noob2000
</script>
Producción:
3
Complejidad de tiempo: O(N)
Complejidad de espacio: O(H) donde H es la altura de BST
Publicación traducida automáticamente
Artículo escrito por DivyanshuShekhar1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA