अवधारणा
दिए गए बाइनरी ट्री के संबंध में, इसके लिए निम्नलिखित मान लौटाएं।
हर स्तर के लिए, यदि उस स्तर पर पत्तियां हैं तो सभी पत्तियों का योग निकालें। अन्यथा इसे अनदेखा करें।
सभी योगों का गुणनफल निकालें और इसे लौटाएं।
इनपुट
निम्नलिखित ट्री का रूट 3 / \ 8 6 \ 10
आउटपुट
80
पहले स्तर में पत्तियां नहीं हैं। दूसरे स्तर में एक पत्ता 8 है और तीसरे स्तर में भी एक पत्ता 10 है। तो परिणाम 8*10 = 80 है
इनपुट
निम्नलिखित ट्री का रूट 3 / \ 8 6 / \ \ 9 7 10 / \ / \ 2 12 5 11
आउटपुट
270
पहले दो स्तरों में पत्तियां नहीं हैं। तीसरे स्तर में एक पत्ता 9 है। अंतिम स्तर में चार पत्तियां 2, 12, 5 और 11 हैं। तो परिणाम 9 * (2 + 12 + 5 + 11) = 270 है
विधि
एक सरल समाधान के लिए, हम शीर्ष से नीचे तक सभी स्तरों के लिए पत्ती योग की पुनरावर्ती गणना करते हैं। उसके बाद उन स्तरों के योगों को गुणा करते हैं जिनमें पत्तियां हैं। यहां, इस समाधान की समय जटिलता O(n^2) होगी।
एक कुशल समाधान के लिए, हम क्यू आधारित लेवल ऑर्डर ट्रैवर्सल का उपयोग करते हैं। ट्रैवर्सल करते समय, हम प्रत्येक अलग स्तर को अलग से संसाधित करते हैं। हर संसाधित स्तर के लिए, जांचें कि क्या इसमें पत्ती है। इस मामले में, यदि है तो पत्ती नोड्स का योग निकालें। अंत में, सभी योगों का गुणनफल लौटाएं।
उदाहरण
/* बाइनरी ट्री के समान स्तर पर सभी पत्तियों के डेटा का योग ढूंढने और फिर सभी स्तरों के प्राप्त योगों को गुणा करने के लिए पुनरावृत्त C++ प्रोग्राम। */ #include <bits/stdc++.h> using namespace std; // बाइनरी ट्री नोड दिखाता है struct Node1 { int data1; struct Node1 *left1, *right1; }; // जांचने के लिए सहायक फ़ंक्शन कि क्या नोड ट्री का पत्ता है bool isLeaf(Node1* root1){ return (!root1->left1 && !root1->right1); } /* प्रत्येक स्तर पर सभी पत्ती नोड्स का योग निकालता है और योगों का गुणनफल लौटाता है */ int sumAndMultiplyLevelData(Node1* root1){ // यहां ट्री खाली है if (!root1) return 0; int mul1 = 1; /* परिणाम संग्रहीत करने के लिए उपयोग किया जाता है */ // लेवल ऑर्डर ट्रैवर्सल के लिए एक खाली क्यू बनाएं queue<Node1*> q1; // रूट को एनक्यू करें और ऊंचाई प्रारंभ करें q1.push(root1); // ट्री का लेवल ऑर्डर ट्रैवर्सल करें while (1) { // NodeCount1 (क्यू आकार) वर्तमान स्तर पर नोड्स की संख्या दर्शाता है int NodeCount1 = q1.size(); // अब यदि वर्तमान स्तर पर कोई नोड नहीं है, तो हमारा काम हो गया if (NodeCount1 == 0) break; // वर्तमान स्तर के लिए पत्ती योग प्रारंभ करें int levelSum1 = 0; // एक बूलियन चर दिखाता है कि क्या वर्तमान स्तर पर पत्ती नोड मिला या नहीं bool leafFound1 = false; // वर्तमान स्तर के सभी नोड्स को डीक्यू करें और अगले स्तर के सभी नोड्स को एनक्यू करें while (NodeCount1 > 0) { // वर्तमान स्तर के अगले नोड को संसाधित करें Node1* Node1 = q1.front(); /* अब यदि नोड एक पत्ता है, तो स्तर पर योग अपडेट करें */ if (isLeaf(Node1)) { leafFound1 = true; levelSum1 += Node1->data1; } q1.pop(); // नोड के बच्चे जोड़ें if (Node1->left1 != NULL) q1.push(Node1->left1); if (Node1->right1 != NULL) q1.push(Node1->right1); NodeCount1--; } // अब यदि हमें कम से कम एक पत्ता मिला, तो हम परिणाम को स्तर योग से गुणा करते हैं। if (leafFound1) mul1 *= levelSum1; } return mul1; // यहां परिणाम लौटाएं } // नया ट्री नोड बनाने के लिए उपयोगिता फ़ंक्शन दिखाता है Node1* newNode(int data1){ Node1* temp1 = new Node1; temp1->data1 = data1; temp1->left1 = temp1->right1 = NULL; return temp1; } // उपरोक्त फ़ंक्शन का परीक्षण करने के लिए ड्राइवर प्रोग्राम int main(){ Node1* root1 = newNode(3); root1->left1 = newNode(8); root1->right1 = newNode(6); root1->left1->right1 = newNode(7); root1->left1->left1 = newNode(9); root1->left1->right1->left1 = newNode(2); root1->left1->right1->right1 = newNode(12); root1->right1->right1 = newNode(10); root1->right1->right1->left1 = newNode(5); root1->right1->right1->right1 = newNode(11); cout << "अंतिम गुणनफल मान = " << sumAndMultiplyLevelData(root1) <<endl; return 0; }
आउटपुट
अंतिम गुणनफल मान = 270
