मान लीजिए हमारे पास एक बाइनरी ट्री है जिसमें एक रूट नोड और उसका बायां बच्चा और दायां बच्चा है। कार्य ट्री के उन लीफ नोड्स का कुल योग ढूंढना है जो अपने पैरेंट नोड के बाईं ओर हैं।
उदाहरण के लिए
इनपुट-1:
आउटपुट:
15
व्याख्या: दिए गए इनपुट बाइनरी ट्री में, सभी बाएं लीफ नोड्स का योग 9+4+2 = 15 है। इसलिए, आउटपुट 15 है।
इस समस्या को हल करने का दृष्टिकोण
हमारे पास एक बाइनरी ट्री है और कार्य उन सभी लीफ नोड्स का योग ढूंढना है जो अपने पैरेंट के बाईं ओर हैं।
इस समस्या को हल करने का रिकर्सिव दृष्टिकोण यह है कि जांचें कि रूट नोड का बायां नोड खाली है या नहीं। यदि यह खाली है, तो उसके बाएं नोड के लिए योग की गणना करें और दाएं नोड के लिए पुनरावर्ती योग ढूंढें। इस प्रकार, प्रत्येक नोड के लिए, हम पुनरावर्ती रूप से जांचेंगे और उसका योग ढूंढेंगे।
- रूट नोड्स और उसके बाएं बच्चे के साथ-साथ दाएं बच्चे वाले बाइनरी ट्री को इनपुट के रूप में लें।
- एक पूर्णांक फ़ंक्शन leftLeafSum(treenode*root) रूट नोड को इनपुट के रूप में लेता है और उन सभी लीफ नोड्स का योग लौटाता है जो अपने पैरेंट के बाईं ओर हैं।
- यदि रूट नोड खाली या NULL है, तो 'शून्य' लौटाएं अन्यथा रूट नोड के बाएं नोड की जांच करें।
- यदि रूट नोड का बायां नोड बिना किसी बच्चे के है, तो दाएं नोड के लिए पुनरावर्ती रूप से जांचें।
- बाएं बच्चे और दाएं बच्चे के लिए पुनरावर्ती रूप से योग लौटाएं।
उदाहरण
#include<bits/stdc++.h>
using namespace std;
struct treenode {
int data;
treenode * left;
treenode * right;
};
struct treenode * createNode(int d) {
struct treenode * root = new treenode;
root -> data = d;
root -> left = NULL;
root -> right = NULL;
return root;
}
int leftLeafSum(treenode * root) {
if (root == NULL) {
return 0;
}
if (root -> left and!root -> left -> left and!root -> left -> right) {
return root -> left -> data + leftLeafSum(root -> right);
}
return leftLeafSum(root -> left) + leftLeafSum(root -> right);
}
int main() {
struct treenode * root = NULL;
root = createNode(4);
root -> left = createNode(2);
root -> right = createNode(2);
root -> left -> right = createNode(7);
root -> left -> left = createNode(5);
root -> right -> left = createNode(5);
root -> right -> right = createNode(7);
int sum = leftLeafSum(root);
cout << sum << endl;
return 0;
}
उपरोक्त कोड चलाने से आउटपुट इस प्रकार उत्पन्न होगा,
आउटपुट
10
व्याख्या: बाएं नोड्स में लीफ नोड्स 5 और 5 हैं जो अपने पैरेंट के बाईं ओर हैं, इस प्रकार सभी लीफ नोड्स का योग = 10 है।
