Dado un árbol binario que contiene n números distintos y un valor x . El problema es contar pares en el árbol binario dado cuya suma es igual al valor x dado .
Ejemplos:
Input :
5
/ \
3 7
/ \ / \
2 4 6 8
x = 10
Output : 3
The pairs are (3, 7), (2, 8) and (4, 6).
1) Enfoque ingenuo: obtenga uno por uno cada Node del árbol binario a través de cualquiera de los métodos transversales de árbol. Pase el Node, digamos temp , la raíz del árbol y el valor x a otra función, digamos findPair() . En la función, con la ayuda del puntero raíz , recorra el árbol nuevamente. Uno por uno, sume estos Nodes con temp y verifique si sum == x. Si es así, incremente el conteo . Calcular cuenta = cuenta / 2 ya que un solo par ha sido contado dos veces por el método mencionado anteriormente.
C++
// C++ implementation to count pairs in a binary tree
// whose sum is equal to given value x
#include <bits/stdc++.h>
using namespace std;
// structure of a node of a binary tree
struct Node {
int data;
Node *left, *right;
};
// function to create and return a node
// of a binary tree
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;
}
// returns true if a pair exists with given sum 'x'
bool findPair(Node* root, Node* temp, int x)
{
// base case
if (!root)
return false;
// pair exists
if (root != temp && ((root->data + temp->data) == x))
return true;
// find pair in left and right subtress
if (findPair(root->left, temp, x) || findPair(root->right, temp, x))
return true;
// pair does not exists with given sum 'x'
return false;
}
// function to count pairs in a binary tree
// whose sum is equal to given value x
void countPairs(Node* root, Node* curr, int x, int& count)
{
// if tree is empty
if (!curr)
return;
// check whether pair exists for current node 'curr'
// in the binary tree that sum up to 'x'
if (findPair(root, curr, x))
count++;
// recursively count pairs in left subtree
countPairs(root, curr->left, x, count);
// recursively count pairs in right subtree
countPairs(root, curr->right, x, count);
}
// Driver program to test above
int main()
{
// formation of binary tree
Node* root = getNode(5); /* 5 */
root->left = getNode(3); /* / \ */
root->right = getNode(7); /* 3 7 */
root->left->left = getNode(2); /* / \ / \ */
root->left->right = getNode(4); /* 2 4 6 8 */
root->right->left = getNode(6);
root->right->right = getNode(8);
int x = 10;
int count = 0;
countPairs(root, root, x, count);
count = count / 2;
cout << "Count = " << count;
return 0;
}
Java
// Java implementation to count pairs in a binary tree
// whose sum is equal to given value x
import java.util.*;
class GFG
{
// structure of a node of a binary tree
static class Node
{
int data;
Node left, right;
};
static int count;
// function to create and return a node
// of a binary tree
static Node getNode(int data)
{
// allocate space for the node
Node new_node = new Node();
// put in the data
new_node.data = data;
new_node.left = new_node.right = null;
return new_node;
}
// returns true if a pair exists with given sum 'x'
static boolean findPair(Node root, Node temp, int x)
{
// base case
if (root==null)
return false;
// pair exists
if (root != temp && ((root.data + temp.data) == x))
return true;
// find pair in left and right subtress
if (findPair(root.left, temp, x) ||
findPair(root.right, temp, x))
return true;
// pair does not exists with given sum 'x'
return false;
}
// function to count pairs in a binary tree
// whose sum is equal to given value x
static void countPairs(Node root, Node curr, int x)
{
// if tree is empty
if (curr == null)
return;
// check whether pair exists for current node 'curr'
// in the binary tree that sum up to 'x'
if (findPair(root, curr, x))
count++;
// recursively count pairs in left subtree
countPairs(root, curr.left, x);
// recursively count pairs in right subtree
countPairs(root, curr.right, x);
}
// Driver code
public static void main(String[] args)
{
// formation of binary tree
Node root = getNode(5); /* 5 */
root.left = getNode(3); /* / \ */
root.right = getNode(7); /* 3 7 */
root.left.left = getNode(2); /* / \ / \ */
root.left.right = getNode(4); /* 2 4 6 8 */
root.right.left = getNode(6);
root.right.right = getNode(8);
int x = 10;
count = 0;
countPairs(root, root, x);
count = count / 2;
System.out.print("Count = " + count);
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 implementation to count pairs in a binary tree
# whose sum is equal to given value x
# structure of a node of a binary tree
class getNode(object):
def __init__(self, value):
self.data = value
self.left = None
self.right = None
# returns True if a pair exists with given sum 'x'
def findPair(root, temp, x):
# base case
if root == None:
return False
# pair exists
if (root != temp and ((root.data + temp.data) == x)):
return True
# find pair in left and right subtress
if (findPair(root.left, temp, x) or findPair(root.right, temp, x)):
return True
# pair does not exists with given sum 'x'
return False
# function to count pairs in a binary tree
# whose sum is equal to given value x
def countPairs(root, curr, x):
global count
# if tree is empty
if curr == None:
return
# check whether pair exists for current node 'curr'
# in the binary tree that sum up to 'x'
if (findPair(root, curr, x)):
count += 1
# recursively count pairs in left subtree
countPairs(root, curr.left, x)
# recursively count pairs in right subtree
countPairs(root, curr.right, x)
# Driver program to test above
# formation of binary tree
root = getNode(5)
root.left = getNode(3)
root.right = getNode(7)
root.left.left = getNode(2)
root.left.right = getNode(4)
root.right.left = getNode(6)
root.right.right = getNode(8)
x = 10
count = 0
countPairs(root, root, x)
count = count // 2
print("Count =", count)
# This code is contributed by shubhamsingh10
C#
// C# implementation to count pairs in a binary tree
// whose sum is equal to given value x
using System;
class GFG
{
// structure of a node of a binary tree
class Node
{
public int data;
public Node left, right;
};
static int count;
// function to create and return a node
// of a binary tree
static Node getNode(int data)
{
// allocate space for the node
Node new_node = new Node();
// put in the data
new_node.data = data;
new_node.left = new_node.right = null;
return new_node;
}
// returns true if a pair exists with given sum 'x'
static bool findPair(Node root, Node temp, int x)
{
// base case
if (root == null)
return false;
// pair exists
if (root != temp && ((root.data + temp.data) == x))
return true;
// find pair in left and right subtress
if (findPair(root.left, temp, x) ||
findPair(root.right, temp, x))
return true;
// pair does not exists with given sum 'x'
return false;
}
// function to count pairs in a binary tree
// whose sum is equal to given value x
static void countPairs(Node root, Node curr, int x)
{
// if tree is empty
if (curr == null)
return;
// check whether pair exists for current node 'curr'
// in the binary tree that sum up to 'x'
if (findPair(root, curr, x))
count++;
// recursively count pairs in left subtree
countPairs(root, curr.left, x);
// recursively count pairs in right subtree
countPairs(root, curr.right, x);
}
// Driver code
public static void Main(String[] args)
{
// formation of binary tree
Node root = getNode(5); /* 5 */
root.left = getNode(3); /* / \ */
root.right = getNode(7); /* 3 7 */
root.left.left = getNode(2); /* / \ / \ */
root.left.right = getNode(4); /* 2 4 6 8 */
root.right.left = getNode(6);
root.right.right = getNode(8);
int x = 10;
count = 0;
countPairs(root, root, x);
count = count / 2;
Console.Write("Count = " + count);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript implementation to count
// pairs in a binary tree whose sum is
// equal to given value x
// Structure of a node of a binary tree
class Node
{
constructor()
{
this.data = 0;
this.left = null;
this.right = null;
}
};
var count = 0;
// Function to create and return a node
// of a binary tree
function getNode(data)
{
// Allocate space for the node
var new_node = new Node();
// Put in the data
new_node.data = data;
new_node.left = new_node.right = null;
return new_node;
}
// Returns true if a pair exists
// with given sum 'x'
function findPair(root, temp, x)
{
// Base case
if (root == null)
return false;
// Pair exists
if (root != temp &&
((root.data + temp.data) == x))
return true;
// Find pair in left and right subtress
if (findPair(root.left, temp, x) ||
findPair(root.right, temp, x))
return true;
// Pair does not exists with given sum 'x'
return false;
}
// Function to count pairs in a binary tree
// whose sum is equal to given value x
function countPairs( root, curr, x)
{
// If tree is empty
if (curr == null)
return;
// Check whether pair exists for current node
// 'curr' in the binary tree that sum up to 'x'
if (findPair(root, curr, x))
count++;
// Recursively count pairs in left subtree
countPairs(root, curr.left, x);
// Recursively count pairs in right subtree
countPairs(root, curr.right, x);
}
// Driver code
// Formation of binary tree
var root = getNode(5); /* 5 */
root.left = getNode(3); /* / \ */
root.right = getNode(7); /* 3 7 */
root.left.left = getNode(2); /* / \ / \ */
root.left.right = getNode(4); /* 2 4 6 8 */
root.right.left = getNode(6);
root.right.right = getNode(8);
var x = 10;
count = 0;
countPairs(root, root, x);
count = parseInt(count / 2);
document.write("Count = " + count);
// This code is contributed by noob2000
</script>
Producción:
Count = 3
Complejidad de tiempo: O(n^2).
2) Enfoque eficiente: Los siguientes son los pasos:
- Convierta el árbol binario dado en una lista doblemente enlazada. Consulte esta publicación.
- Ordene la lista doblemente enlazada obtenida en el Paso 1. Consulte esta publicación.
- Cuente los pares ordenados doblemente vinculados con una suma igual a ‘x’. Consulte esta publicación.
- Muestre el conteo obtenido en el Paso 4.
C++
// C++ implementation to count pairs in a binary tree
// whose sum is equal to given value x
#include <bits/stdc++.h>
using namespace std;
// structure of a node of a binary tree
struct Node {
int data;
Node *left, *right;
};
// function to create and return a node
// of a binary tree
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;
}
// A simple recursive function to convert a given
// Binary tree to Doubly Linked List
// root --> Root of Binary Tree
// head_ref --> Pointer to head node of created
// doubly linked list
void BToDLL(Node* root, Node** head_ref)
{
// Base cases
if (root == NULL)
return;
// Recursively convert right subtree
BToDLL(root->right, head_ref);
// insert root into DLL
root->right = *head_ref;
// Change left pointer of previous head
if (*head_ref != NULL)
(*head_ref)->left = root;
// Change head of Doubly linked list
*head_ref = root;
// Recursively convert left subtree
BToDLL(root->left, head_ref);
}
// Split a doubly linked list (DLL) into 2 DLLs of
// half sizes
Node* split(Node* head)
{
Node *fast = head, *slow = head;
while (fast->right && fast->right->right) {
fast = fast->right->right;
slow = slow->right;
}
Node* temp = slow->right;
slow->right = NULL;
return temp;
}
// Function to merge two sorted doubly linked lists
Node* merge(Node* first, Node* second)
{
// If first linked list is empty
if (!first)
return second;
// If second linked list is empty
if (!second)
return first;
// Pick the smaller value
if (first->data < second->data) {
first->right = merge(first->right, second);
first->right->left = first;
first->left = NULL;
return first;
}
else {
second->right = merge(first, second->right);
second->right->left = second;
second->left = NULL;
return second;
}
}
// Function to do merge sort
Node* mergeSort(Node* head)
{
if (!head || !head->right)
return head;
Node* second = split(head);
// Recur for left and right halves
head = mergeSort(head);
second = mergeSort(second);
// Merge the two sorted halves
return merge(head, second);
}
// Function to count pairs in a sorted doubly linked list
// whose sum equal to given value x
int pairSum(Node* head, int x)
{
// Set two pointers, first to the beginning of DLL
// and second to the end of DLL.
Node* first = head;
Node* second = head;
while (second->right != NULL)
second = second->right;
int count = 0;
// The loop terminates when either of two pointers
// become NULL, or they cross each other (second->right
// == first), or they become same (first == second)
while (first != NULL && second != NULL && first != second && second->right != first) {
// pair found
if ((first->data + second->data) == x) {
count++;
// move first in forward direction
first = first->right;
// move second in backward direction
second = second->left;
}
else {
if ((first->data + second->data) < x)
first = first->right;
else
second = second->left;
}
}
return count;
}
// function to count pairs in a binary tree
// whose sum is equal to given value x
int countPairs(Node* root, int x)
{
Node* head = NULL;
int count = 0;
// Convert binary tree to
// doubly linked list
BToDLL(root, &head);
// sort DLL
head = mergeSort(head);
// count pairs
return pairSum(head, x);
}
// Driver program to test above
int main()
{
// formation of binary tree
Node* root = getNode(5); /* 5 */
root->left = getNode(3); /* / \ */
root->right = getNode(7); /* 3 7 */
root->left->left = getNode(2); /* / \ / \ */
root->left->right = getNode(4); /* 2 4 6 8 */
root->right->left = getNode(6);
root->right->right = getNode(8);
int x = 10;
cout << "Count = "
<< countPairs(root, x);
return 0;
}
Java
// Java implementation to count pairs
// in a binary tree whose sum is equal to
// given value x
class GFG
{
// structure of a node of a binary tree
static class Node
{
int data;
Node left, right;
};
static Node head_ref;
// function to create and return a node
// of a binary tree
static Node getNode(int data)
{
// allocate space for the node
Node new_node = new Node();
// put in the data
new_node.data = data;
new_node.left = new_node.right = null;
return new_node;
}
// A simple recursive function to convert
// a given Binary tree to Doubly Linked List
// root -. Root of Binary Tree
// head_ref -. Pointer to head node of created
// doubly linked list
static void BToDLL(Node root)
{
// Base cases
if (root == null)
return;
// Recursively convert right subtree
BToDLL(root.right);
// insert root into DLL
root.right = head_ref;
// Change left pointer of previous head
if (head_ref != null)
head_ref.left = root;
// Change head of Doubly linked list
head_ref = root;
// Recursively convert left subtree
BToDLL(root.left);
}
// Split a doubly linked list (DLL)
// into 2 DLLs of half sizes
static Node split(Node head)
{
Node fast = head, slow = head;
while (fast.right != null &&
fast.right.right != null)
{
fast = fast.right.right;
slow = slow.right;
}
Node temp = slow.right;
slow.right = null;
return temp;
}
// Function to merge two sorted
// doubly linked lists
static Node merge(Node first, Node second)
{
// If first linked list is empty
if (first == null)
return second;
// If second linked list is empty
if (second == null)
return first;
// Pick the smaller value
if (first.data < second.data)
{
first.right = merge(first.right,
second);
first.right.left = first;
first.left = null;
return first;
}
else
{
second.right = merge(first,
second.right);
second.right.left = second;
second.left = null;
return second;
}
}
// Function to do merge sort
static Node mergeSort(Node head)
{
if (head == null || head.right == null)
return head;
Node second = split(head);
// Recur for left and right halves
head = mergeSort(head);
second = mergeSort(second);
// Merge the two sorted halves
return merge(head, second);
}
// Function to count pairs in a sorted
// doubly linked list whose sum equal
// to given value x
static int pairSum(Node head, int x)
{
// Set two pointers, first to the beginning
// of DLL and second to the end of DLL.
Node first = head;
Node second = head;
while (second.right != null)
second = second.right;
int count = 0;
// The loop terminates when either of two pointers
// become null, or they cross each other (second.right
// == first), or they become same (first == second)
while (first != null && second != null &&
first != second && second.right != first)
{
// pair found
if ((first.data + second.data) == x)
{
count++;
// move first in forward direction
first = first.right;
// move second in backward direction
second = second.left;
}
else
{
if ((first.data + second.data) < x)
first = first.right;
else
second = second.left;
}
}
return count;
}
// function to count pairs in a binary tree
// whose sum is equal to given value x
static int countPairs(Node root, int x)
{
head_ref = null;
// Convert binary tree to
// doubly linked list
BToDLL(root);
// sort DLL
head_ref = mergeSort(head_ref);
// count pairs
return pairSum(head_ref, x);
}
// Driver Code
public static void main(String[] args)
{
// formation of binary tree
Node root = getNode(5); /* 5 */
root.left = getNode(3); /* / \ */
root.right = getNode(7); /* 3 7 */
root.left.left = getNode(2); /* / \ / \ */
root.left.right = getNode(4); /* 2 4 6 8 */
root.right.left = getNode(6);
root.right.right = getNode(8);
int x = 10;
System.out.print("Count = " +
countPairs(root, x));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 implementation to count pairs in a binary tree
# whose sum is equal to given value x
# structure of a node of a binary tree
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
head_ref = None
# function to create and return a node
# of a binary tree
def getNode(data):
# allocate space for the node
new_node = Node(data)
return new_node
# A simple recursive function to convert a given
# Binary tree to Doubly Linked List
# root -. Root of Binary Tree
# head_ref -. Pointer to head node of created
# doubly linked list
def BToDLL(root):
global head_ref
# Base cases
if (root == None):
return;
# Recursively convert right subtree
BToDLL(root.right)
# insert root into DLL
root.right = head_ref;
# Change left pointer of previous head
if (head_ref != None):
(head_ref).left = root;
# Change head of Doubly linked list
head_ref = root;
# Recursively convert left subtree
BToDLL(root.left);
return head_ref
# Split a doubly linked list (DLL) into 2 DLLs of
# half sizes
def split(head):
fast = head
slow = head;
while (fast.right and fast.right.right):
fast = fast.right.right;
slow = slow.right;
temp = slow.right;
slow.right = None;
return temp;
# Function to merge two sorted doubly linked lists
def merge(first, second):
# If first linked list is empty
if (not first):
return second;
# If second linked list is empty
if (not second):
return first;
# Pick the smaller value
if (first.data < second.data):
first.right = merge(first.right, second);
first.right.left = first;
first.left = None;
return first;
else:
second.right = merge(first, second.right);
second.right.left = second;
second.left = None;
return second;
# Function to do merge sort
def mergeSort(head):
if (head == None or head.right == None):
return head;
second = split(head);
# Recur for left and right halves
head = mergeSort(head);
second = mergeSort(second);
# Merge the two sorted halves
return merge(head, second);
# Function to count pairs in a sorted doubly linked list
# whose sum equal to given value x
def pairSum(head, x):
# Set two pointers, first to the beginning of DLL
# and second to the end of DLL.
first = head;
second = head;
while (second.right != None):
second = second.right;
count = 0;
# The loop terminates when either of two pointers
# become None, or they cross each other (second.right
# == first), or they become same (first == second)
while (first != None and second != None and first != second and second.right != first):
# pair found
if ((first.data + second.data) == x):
count += 1
# move first in forward direction
first = first.right;
# move second in backward direction
second = second.left;
else:
if ((first.data + second.data) < x):
first = first.right;
else:
second = second.left;
return count;
# function to count pairs in a binary tree
# whose sum is equal to given value x
def countPairs(root, x):
global head_ref
head_ref = None;
# Convert binary tree to
# doubly linked list
BToDLL(root);
# sort DLL
head_ref = mergeSort(head_ref);
# count pairs
return pairSum(head_ref, x);
# Driver code
if __name__=='__main__':
# formation of binary tree
root = getNode(5); # 5
root.left = getNode(3); # / \
root.right = getNode(7); # 3 7
root.left.left = getNode(2); # / \ / \
root.left.right = getNode(4);# 2 4 6 8
root.right.left = getNode(6);
root.right.right = getNode(8);
x = 10;
print("Count = " + str(countPairs(root, x)))
# This code is contributed by rutvik_56
C#
// C# implementation to count pairs
// in a binary tree whose sum is
// equal to the given value x
using System;
class GFG
{
// structure of a node of a binary tree
class Node
{
public int data;
public Node left, right;
};
static Node head_ref;
// function to create and return a node
// of a binary tree
static Node getNode(int data)
{
// allocate space for the node
Node new_node = new Node();
// put in the data
new_node.data = data;
new_node.left = new_node.right = null;
return new_node;
}
// A simple recursive function to convert
// a given Binary tree to Doubly Linked List
// root -. Root of Binary Tree
// head_ref -. Pointer to head node of
// created doubly linked list
static void BToDLL(Node root)
{
// Base cases
if (root == null)
return;
// Recursively convert right subtree
BToDLL(root.right);
// insert root into DLL
root.right = head_ref;
// Change left pointer of previous head
if (head_ref != null)
head_ref.left = root;
// Change head of Doubly linked list
head_ref = root;
// Recursively convert left subtree
BToDLL(root.left);
}
// Split a doubly linked list (DLL)
// into 2 DLLs of half sizes
static Node split(Node head)
{
Node fast = head, slow = head;
while (fast.right != null &&
fast.right.right != null)
{
fast = fast.right.right;
slow = slow.right;
}
Node temp = slow.right;
slow.right = null;
return temp;
}
// Function to merge two sorted
// doubly linked lists
static Node merge(Node first,
Node second)
{
// If first linked list is empty
if (first == null)
return second;
// If second linked list is empty
if (second == null)
return first;
// Pick the smaller value
if (first.data < second.data)
{
first.right = merge(first.right,
second);
first.right.left = first;
first.left = null;
return first;
}
else
{
second.right = merge(first,
second.right);
second.right.left = second;
second.left = null;
return second;
}
}
// Function to do merge sort
static Node mergeSort(Node head)
{
if (head == null || head.right == null)
return head;
Node second = split(head);
// Recur for left and right halves
head = mergeSort(head);
second = mergeSort(second);
// Merge the two sorted halves
return merge(head, second);
}
// Function to count pairs in a sorted
// doubly linked list whose sum equal
// to given value x
static int pairSum(Node head, int x)
{
// Set two pointers, first to the beginning
// of DLL and second to the end of DLL.
Node first = head;
Node second = head;
while (second.right != null)
second = second.right;
int count = 0;
// The loop terminates when either of
// two pointers become null, or they
// cross each other (second.right == first),
// or they become same (first == second)
while (first != null && second != null &&
first != second && second.right != first)
{
// pair found
if ((first.data + second.data) == x)
{
count++;
// move first in forward direction
first = first.right;
// move second in backward direction
second = second.left;
}
else
{
if ((first.data + second.data) < x)
first = first.right;
else
second = second.left;
}
}
return count;
}
// function to count pairs in a binary tree
// whose sum is equal to given value x
static int countPairs(Node root, int x)
{
head_ref = null;
// Convert binary tree to
// doubly linked list
BToDLL(root);
// sort DLL
head_ref = mergeSort(head_ref);
// count pairs
return pairSum(head_ref, x);
}
// Driver Code
public static void Main(String[] args)
{
// formation of binary tree
Node root = getNode(5); /* 5 */
root.left = getNode(3); /* / \ */
root.right = getNode(7); /* 3 7 */
root.left.left = getNode(2); /* / \ / \ */
root.left.right = getNode(4); /* 2 4 6 8 */
root.right.left = getNode(6);
root.right.right = getNode(8);
int x = 10;
Console.Write("Count = " +
countPairs(root, x));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript implementation to count pairs
// in a binary tree whose sum is
// equal to the given value x
// structure of a node of a binary tree
class Node {
constructor() {
this.data = 0;
this.left = null;
this.right = null;
}
}
var head_ref = null;
// function to create and return a node
// of a binary tree
function getNode(data) {
// allocate space for the node
var new_node = new Node();
// put in the data
new_node.data = data;
new_node.left = new_node.right = null;
return new_node;
}
// A simple recursive function to convert
// a given Binary tree to Doubly Linked List
// root -. Root of Binary Tree
// head_ref -. Pointer to head node of
// created doubly linked list
function BToDLL(root) {
// Base cases
if (root == null) return;
// Recursively convert right subtree
BToDLL(root.right);
// insert root into DLL
root.right = head_ref;
// Change left pointer of previous head
if (head_ref != null) head_ref.left = root;
// Change head of Doubly linked list
head_ref = root;
// Recursively convert left subtree
BToDLL(root.left);
}
// Split a doubly linked list (DLL)
// into 2 DLLs of half sizes
function split(head) {
var fast = head,
slow = head;
while (fast.right != null && fast.right.right != null) {
fast = fast.right.right;
slow = slow.right;
}
var temp = slow.right;
slow.right = null;
return temp;
}
// Function to merge two sorted
// doubly linked lists
function merge(first, second) {
// If first linked list is empty
if (first == null) return second;
// If second linked list is empty
if (second == null) return first;
// Pick the smaller value
if (first.data < second.data) {
first.right = merge(first.right, second);
first.right.left = first;
first.left = null;
return first;
} else {
second.right = merge(first, second.right);
second.right.left = second;
second.left = null;
return second;
}
}
// Function to do merge sort
function mergeSort(head) {
if (head == null || head.right == null) return head;
var second = split(head);
// Recur for left and right halves
head = mergeSort(head);
second = mergeSort(second);
// Merge the two sorted halves
return merge(head, second);
}
// Function to count pairs in a sorted
// doubly linked list whose sum equal
// to given value x
function pairSum(head, x) {
// Set two pointers, first to the beginning
// of DLL and second to the end of DLL.
var first = head;
var second = head;
while (second.right != null) second = second.right;
var count = 0;
// The loop terminates when either of
// two pointers become null, or they
// cross each other (second.right == first),
// or they become same (first == second)
while (
first != null &&
second != null &&
first != second &&
second.right != first
) {
// pair found
if (first.data + second.data == x) {
count++;
// move first in forward direction
first = first.right;
// move second in backward direction
second = second.left;
} else {
if (first.data + second.data < x) first = first.right;
else second = second.left;
}
}
return count;
}
// function to count pairs in a binary tree
// whose sum is equal to given value x
function countPairs(root, x) {
head_ref = null;
// Convert binary tree to
// doubly linked list
BToDLL(root);
// sort DLL
head_ref = mergeSort(head_ref);
// count pairs
return pairSum(head_ref, x);
}
// Driver Code
// formation of binary tree
var root = getNode(5); /* 5 */
root.left = getNode(3); /* / \ */
root.right = getNode(7); /* 3 7 */
root.left.left = getNode(2); /* / \ / \ */
root.left.right = getNode(4); /* 2 4 6 8 */
root.right.left = getNode(6);
root.right.right = getNode(8);
var x = 10;
document.write("Count = " + countPairs(root, x));
</script>
Producción:
Count = 3
Complejidad temporal: O(nLog n).
3) Otro enfoque eficiente: no es necesario convertir a DLL y clasificar: los siguientes son los pasos:
- Atraviesa el árbol en cualquier orden (pre/post/in).
- Cree un hash vacío y siga agregando la diferencia entre el valor del Node actual y X.
- En cada Node, verifique si su valor está en el hash, si es así, incremente el conteo en 1 y NO agregue la diferencia del valor de este Node con X en el hash para evitar el conteo duplicado para un solo par.
Java
// Java program to Count pairs
// in a binary tree whose sum is
// equal to a given value x
import java.util.HashSet;
public class GFG
{
// Node class to represent a
// node in the binary tree
// with value, left and right attributes
static class Node {
int value;
Node left, right;
public Node(int value) {
this.value = value;
}
}
// To store count of pairs
static int count = 0;
// To store difference between
// current node's value and x,
// acts a lookup for counting pairs
static HashSet<Integer> hash_t = new HashSet<Integer>();
// The input, we need to count
// pairs whose sum is equal to x
static int x = 10;
// Function to count number of pairs
// Does a pre-order traversal of the tree
static void count_pairs_w_sum(Node root) {
if( root != null) {
if (hash_t.contains(root.value))
count += 1;
else
hash_t.add(x-root.value);
count_pairs_w_sum(root.left);
count_pairs_w_sum(root.right);
}
}
//Driver method
public static void main(String[] args) {
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);
count_pairs_w_sum(root);
System.out.println(count);
}
}
// This code is contributed by Lovely Jain
Python
# Python program to Count pairs # in a binary tree whose sum is # equal to a given value x # Node class to represent a # node in the binary tree # with value, left and right attributes class Node(object): def __init__(self, value, left=None, right=None): self.value = value self.left = left self.right = right # To store count of pairs count = 0 # To store difference between # current node's value and x, # acts a lookup for counting pairs hash_t = set() # The input, we need to count # pairs whose sum is equal to x x = 10 # Function to count number of pairs # Does a pre-order traversal of the tree def count_pairs_w_sum(root): global count if root: if root.value in hash_t: count += 1 else: hash_t.add(x-root.value) count_pairs_w_sum(root.left) count_pairs_w_sum(root.right) # Entry point / Driver - Create a # binary tree and call the function # to get the count if __name__ == '__main__': 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) count_pairs_w_sum(root) print count
Producción:
Count = 3
Complejidad temporal: O(n)
Complejidad espacial: O(n)
Publicación traducida automáticamente
Artículo escrito por ayushjauhari14 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA