इस समस्या में हमें एक Binary Tree दिया जाता है। और हमें यह पता लगाने की जरूरत है कि क्या रूट के डेटा के बराबर योग के साथ लीफ पाथ में रूट में कोई जोड़ा है।
हमें यह जांचने की आवश्यकता है कि क्या नोड्स की एक जोड़ी मौजूद है जो रूट नोड से लीफ नोड्स के बीच स्थित है, ताकि जोड़े के मानों का योग रूट नोड के मान के बराबर हो।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट:
<मजबूत> 
आउटपुट: हाँ
स्पष्टीकरण:
रूट नोड मान 7
रूट नोड, (2, 5), (1, 6) के बराबर योग मान वाले जोड़े।
समाधान दृष्टिकोण:
हमें पेड़ को पार करने और हैशिंग का उपयोग करके जोड़े खोजने की जरूरत है।
इसके लिए हम एक हैशटेबल और ट्रैवर्स ट्री बनाएंगे। हैशटेबल में डेटा डालें और फिर जांचें कि अन्य तत्वों के साथ इसका योग रूट के बराबर है या नहीं।
और अंत में, अगर हमें कोई जोड़ा नहीं मिलता है, तो झूठा लौटाएं।
यदि जोड़े पाए जाते हैं, तो सत्य लौटाएं।
हमारे समाधान की कार्यप्रणाली को दर्शाने वाला कार्यक्रम,
उदाहरण
#include<bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* left, *right;
};
struct Node* newnode(int data) {
struct Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return (node);
}
bool findSumUntill(Node *node, unordered_set<int> &hashTable, int rootVal)
{
if (node == NULL)
return false;
int otherVal = rootVal - node->data;
if (hashTable.find(otherVal) != hashTable.end())
return true;
hashTable.insert(node->data);
bool isFound = findSumUntill(node->left, hashTable, rootVal) || findSumUntill(node->right, hashTable, rootVal);
hashTable.erase(node->data);
return isFound;
}
bool findPairSum(Node *root) {
unordered_set<int> hashTable;
return findSumUntill(root->left, hashTable, root->data) || findSumUntill(root->right, hashTable, root->data);
}
int main()
{
struct Node *root = newnode(7);
root->left = newnode(2);
root->right = newnode(3);
root->left->left = newnode(5);
root->left->right = newnode(9);
root->left->left->left = newnode(1);
root->left->left->right = newnode(6);
root->right->left = newnode(8);
if(findPairSum(root))
cout<<"Pair with sum equal to root value found";
else
cout<<"No pairs found";
return 0;
} आउटपुट
Pair with sum equal to root value found