इस समस्या में, हमें एक बाइनरी ट्री दिया गया है। और हमें जांचना है कि क्या रूट से लीफ पथ में कोई जोड़ा है जिसका योग रूट के डेटा के बराबर है।
हमें जांचना है कि क्या नोड्स का कोई जोड़ा मौजूद है जो रूट नोड से लीफ नोड्स के बीच स्थित है जैसे कि जोड़े के मानों का योग रूट नोड के मान के बराबर है।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट:
आउटपुट: Yes
व्याख्या:
रूट नोड मान 7
रूट नोड के बराबर योग वाले जोड़े, (2, 5), (1, 6)।
समाधान दृष्टिकोण:
हमें ट्री को ट्रैवर्स करना होगा और हैशिंग का उपयोग करके जोड़े ढूंढने होंगे।
इसके लिए हम एक हैश टेबल बनाएंगे और ट्री को ट्रैवर्स करेंगे। डेटा को हैशटेबल में डालें और फिर जांचें कि क्या इसका योग अन्य तत्वों के साथ रूट के बराबर है।
और अंत में, यदि हमें कोई जोड़ा नहीं मिलता है, तो false वापस करें।
यदि जोड़े मिलते हैं, तो true वापस करें।
हमारे समाधान की कार्यप्रणाली को दर्शाने वाला प्रोग्राम,
उदाहरण
#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
