Dado un BST y una suma, encuentre si hay un par con la suma dada.
Ejemplo:
C++
// CPP program to find a pair with
// given sum using hashing
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node *left, *right;
};
Node* NewNode(int data)
{
Node* temp = (Node*)malloc(sizeof(Node));
temp->data = data;
temp->left = NULL;
temp->right = NULL;
return temp;
}
Node* insert(Node* root, int key)
{
if (root == NULL)
return NewNode(key);
if (key < root->data)
root->left = insert(root->left, key);
else
root->right = insert(root->right, key);
return root;
}
bool findpairUtil(Node* root, int sum,
unordered_set<int>& set)
{
if (root == NULL)
return false;
if (findpairUtil(root->left, sum, set))
return true;
if (set.find(sum - root->data) != set.end()) {
cout << "Pair is found (" << sum - root->data
<< ", " << root->data << ")" << endl;
return true;
}
else
set.insert(root->data);
return findpairUtil(root->right, sum, set);
}
void findPair(Node* root, int sum)
{
unordered_set<int> set;
if (!findpairUtil(root, sum, set))
cout << "Pairs do not exit" << endl;
}
// Driver code
int main()
{
Node* root = NULL;
root = insert(root, 15);
root = insert(root, 10);
root = insert(root, 20);
root = insert(root, 8);
root = insert(root, 12);
root = insert(root, 16);
root = insert(root, 25);
root = insert(root, 10);
int sum = 33;
findPair(root, sum);
return 0;
}
Java
// JAVA program to find a pair with
// given sum using hashing
import java.util.*;
class GFG {
static class Node {
int data;
Node left, right;
};
static Node NewNode(int data)
{
Node temp = new Node();
temp.data = data;
temp.left = null;
temp.right = null;
return temp;
}
static Node insert(Node root, int key)
{
if (root == null)
return NewNode(key);
if (key < root.data)
root.left = insert(root.left, key);
else
root.right = insert(root.right, key);
return root;
}
static boolean findpairUtil(Node root, int sum,
HashSet<Integer> set)
{
if (root == null)
return false;
if (findpairUtil(root.left, sum, set))
return true;
if (set.contains(sum - root.data)) {
System.out.println("Pair is found ("
+ (sum - root.data) + ", "
+ root.data + ")");
return true;
}
else
set.add(root.data);
return findpairUtil(root.right, sum, set);
}
static void findPair(Node root, int sum)
{
HashSet<Integer> set = new HashSet<Integer>();
if (!findpairUtil(root, sum, set))
System.out.print("Pairs do not exit"
+ "\n");
}
// Driver code
public static void main(String[] args)
{
Node root = null;
root = insert(root, 15);
root = insert(root, 10);
root = insert(root, 20);
root = insert(root, 8);
root = insert(root, 12);
root = insert(root, 16);
root = insert(root, 25);
root = insert(root, 10);
int sum = 33;
findPair(root, sum);
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 program to find a pair with
# given sum using hashing
import sys
import math
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def insert(root, data):
if root is None:
return Node(data)
if(data < root.data):
root.left = insert(root.left, data)
if(data > root.data):
root.right = insert(root.right, data)
return root
def findPairUtil(root, summ, unsorted_set):
if root is None:
return False
if findPairUtil(root.left, summ, unsorted_set):
return True
if unsorted_set and (summ-root.data) in unsorted_set:
print("Pair is Found ({},{})".format(summ-root.data, root.data))
return True
else:
unsorted_set.add(root.data)
return findPairUtil(root.right, summ, unsorted_set)
def findPair(root, summ):
unsorted_set = set()
if(not findPairUtil(root, summ, unsorted_set)):
print("Pair do not exist!")
# Driver code
if __name__ == '__main__':
root = None
root = insert(root, 15)
root = insert(root, 10)
root = insert(root, 20)
root = insert(root, 8)
root = insert(root, 12)
root = insert(root, 16)
root = insert(root, 25)
root = insert(root, 10)
summ = 33
findPair(root, summ)
# This code is contributed by Vikash Kumar 37
C#
// C# program to find a pair with
// given sum using hashing
using System;
using System.Collections.Generic;
class GFG {
class Node {
public int data;
public Node left, right;
};
static Node NewNode(int data)
{
Node temp = new Node();
temp.data = data;
temp.left = null;
temp.right = null;
return temp;
}
static Node insert(Node root, int key)
{
if (root == null)
return NewNode(key);
if (key < root.data)
root.left = insert(root.left, key);
else
root.right = insert(root.right, key);
return root;
}
static bool findpairUtil(Node root, int sum,
HashSet<int> set)
{
if (root == null)
return false;
if (findpairUtil(root.left, sum, set))
return true;
if (set.Contains(sum - root.data)) {
Console.WriteLine("Pair is found ("
+ (sum - root.data) + ", "
+ root.data + ")");
return true;
}
else
set.Add(root.data);
return findpairUtil(root.right, sum, set);
}
static void findPair(Node root, int sum)
{
HashSet<int> set = new HashSet<int>();
if (!findpairUtil(root, sum, set))
Console.Write("Pairs do not exit"
+ "\n");
}
// Driver code
public static void Main(String[] args)
{
Node root = null;
root = insert(root, 15);
root = insert(root, 10);
root = insert(root, 20);
root = insert(root, 8);
root = insert(root, 12);
root = insert(root, 16);
root = insert(root, 25);
root = insert(root, 10);
int sum = 33;
findPair(root, sum);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript program to find a pair with
// given sum using hashing
class Node {
constructor()
{
this.data = 0;
this.left = null;
this.right = null;
}
};
function NewNode(data)
{
var temp = new Node();
temp.data = data;
temp.left = null;
temp.right = null;
return temp;
}
function insert(root, key)
{
if (root == null)
return NewNode(key);
if (key < root.data)
root.left = insert(root.left, key);
else
root.right = insert(root.right, key);
return root;
}
function findpairUtil(root, sum, set)
{
if (root == null)
return false;
if (findpairUtil(root.left, sum, set))
return true;
if (set.has(sum - root.data)) {
document.write("Pair is found ("
+ (sum - root.data) + ", "
+ root.data + ")<br>");
return true;
}
else
set.add(root.data);
return findpairUtil(root.right, sum, set);
}
function findPair(root, sum)
{
var set = new Set();
if (!findpairUtil(root, sum, set))
document.write("Pairs do not exit"
+ "\n");
}
// Driver code
var root = null;
root = insert(root, 15);
root = insert(root, 10);
root = insert(root, 20);
root = insert(root, 8);
root = insert(root, 12);
root = insert(root, 16);
root = insert(root, 25);
root = insert(root, 10);
var sum = 33;
findPair(root, sum);
</script>
Publicación traducida automáticamente
Artículo escrito por aditya1011 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA