मान लीजिए हमारे पास बाइनरी ट्री का रूट नोड है; कार्य हर नोड के टिल्ट का योग ढूंढना और लौटाना है।
बाइनरी ट्री का टिल्ट प्रत्येक लेवल में लेफ्ट सबट्री और राइट सबट्री में चाइल्ड नोड्स के निरपेक्ष अंतर को ढूंढकर बाइनरी ट्री का निर्माण करने के अलावा कुछ नहीं है। किसी विशेष लेवल पर, जिन नोड्स के कोई चाइल्ड नोड्स नहीं हैं, हम उन्हें शून्य से बदलकर केवल टिल्ट करते हैं।
उदाहरण
इनपुट
आउटपुट: 15
व्याख्या: दिए गए बाइनरी ट्री के हर लेवल पर टिल्ट ढूंढना,
नोड 3 का टिल्ट = 0
नोड 5 का टिल्ट = 0
नोड 7 का टिल्ट = 0
नोड 2 का टिल्ट = abs(3-5)= 2
नोड 9 का टिल्ट = abs(0-7)= 7
नोड 4 का टिल्ट = abs((3+5+2)- (9+7))= 6
सभी नोड्स के टिल्ट का योग = 2+7+6= 15
इस समस्या को हल करने का दृष्टिकोण
इस विशेष समस्या को हल करने का सरल दृष्टिकोण पोस्ट ऑर्डर ब्रेडथ फर्स्ट सर्च ट्रैवर्सल का उपयोग करना है।
बाइनरी ट्री को ट्रैवर्स करते समय, हम उसके लेफ्ट सबट्री के सभी नोड्स का योग ढूंढने की कोशिश करेंगे और फिर राइट सबट्री का। एक बार योग मिल जाने पर, हम इसके लेफ्ट सम और राइट सम के निरपेक्ष अंतर की गणना करके सभी नोड्स का टिल्ट ढूंढेंगे।
- एक बाइनरी लें, जो इनपुट होगी।
- एक पूर्णांक फ़ंक्शन sumNodes(treenode*node) ट्री के रूट नोड को लेता है और लेफ्ट सबट्री और राइट सबट्री का योग लौटाता है।
- एक पूर्णांक फ़ंक्शन findTilt(treenode*root) रूट नोड को इनपुट पैरामीटर के रूप में लेता है और सभी नोड्स के टिल्ट का योग लौटाता है।
उदाहरण
#include<iostream>
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 sumNodes(treenode * root, int & sum) {
if (root == NULL) return 0;
int lsum = sumNodes(root -> left, sum);
int rsum = sumNodes(root -> right, sum);
sum += abs(lsum - rsum);
return lsum + rsum + root -> data;
}
int findTilt(treenode * root) {
int sum = 0;
if (root == NULL) {
return 0;
}
sumNodes(root, sum);
return sum;
}
int main() {
struct treenode * root = NULL;
root = createNode(4);
root -> left = createNode(2);
root -> right = createNode(9);
root -> left -> right = createNode(5);
root -> left -> left = createNode(3);
root -> right -> right = createNode(7);
cout << findTilt(root) << endl;
return 0;
}
उपरोक्त कोड चलाने से आउटपुट इस प्रकार उत्पन्न होगा,
आउटपुट
15
दिए गए बाइनरी ट्री में, ट्री के हर लेवल पर सभी नोड्स के टिल्ट का योग 15 है।
