इस समस्या में, हमें एक बाइनरी ट्री दिया गया है। हमारा कार्य दिए गए बाइनरी ट्री में सभी दाएं पत्तियों का योग ज्ञात करना है।
उदाहरण से समझते हैं:
इनपुट:
आउटपुट: 8
व्याख्या:
ट्री के सभी पत्ती नोड्स हैं: 1, 8 योग = 1 + 8 = 9
समाधान दृष्टिकोण
समस्या का एक सरल समाधान ट्री को रूट से पत्ती तक ट्रैवर्स करना है। यदि कोई नोड दायां पत्ता नोड है, तो इसे योग में जोड़ें। जब पूरा ट्री ट्रैवर्स हो जाए, तो योग प्रिंट करें।
उदाहरण
हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम:
#include <iostream> using namespace std; struct Node{ int key; struct Node* left, *right; }; Node *newNode(char k){ Node *node = new Node; node->key = k; node->right = node->left = NULL; return node; } bool isLeafNode(Node *node){ if (node == NULL) return false; if (node->left == NULL && node->right == NULL) return true; return false; } int findRightLeavesSum(Node *root){ int sum = 0; if (root != NULL){ if (isLeafNode(root->right)) sum += root->right->key; else sum += findRightLeavesSum(root->right); sum += findRightLeavesSum(root->left); } return sum; } int main(){ struct Node *root = newNode(5); root->left = newNode(4); root->right = newNode(6); root->left->left = newNode(2); root->left->right = newNode(1); root->right->left = newNode(9); root->right->right = newNode(7); cout<<"The sum of right leaves of the tree is "<<findRightLeavesSum(root); return 0; } आउटपुट
The sum of right leaves of the tree is 8
पुनरावृत्ति का उपयोग करके एक अन्य दृष्टिकोण
हम ट्री पर डेप्थ फर्स्ट सर्च ट्रैवर्सल करेंगे, और फिर जांचेंगे कि क्या वर्तमान नोड दायां पत्ता है। यदि हां, तो इसके मान को योग में जोड़ें, अन्यथा छोड़ दें। अंत में, योग प्रिंट करें।
उदाहरण
हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम:
#include<bits/stdc++.h> using namespace std; struct Node{ int key; struct Node* left, *right; }; Node *newNode(char k){ Node *node = new Node; node->key = k; node->right = node->left = NULL; return node; } int findRightLeavesSum(Node* root){ if(root == NULL) return 0; stack<Node*> treeNodes; treeNodes.push(root); int sum = 0; while(treeNodes.size() > 0){ Node* currentNode = treeNodes.top(); treeNodes.pop(); if (currentNode->right != NULL){ treeNodes.push(currentNode->right); if(currentNode->right->right == NULL && currentNode->right->left == NULL){ sum += currentNode->right->key ; } } if (currentNode->left != NULL) treeNodes.push(currentNode->left); } return sum; } int main(){ Node *root = newNode(5); root->left= newNode(4); root->right = newNode(6); root->left->left = newNode(2); root->left->right = newNode(1); root->right->left = newNode(9); root->right->right= newNode(7); cout<<"The sum of right leaves of the tree is "<<findRightLeavesSum(root); return 0; } आउटपुट
The sum of right leaves of the tree is 8
दृष्टिकोण 3, BFS का उपयोग करके
हम एक ब्रेडथ फर्स्ट सर्च करेंगे जिसमें एक वेरिएबल होगा जो इंगित करेगा कि नोड दायां पत्ता चाइल्ड है या नहीं। यदि है, तो इसे योग में जोड़ें, अन्यथा छोड़ दें। अंत में, योग प्रिंट करें।
उदाहरण
हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम:
#include<bits/stdc++.h> using namespace std; struct Node{ int key; struct Node* left, *right; }; Node *newNode(char k){ Node *node = new Node; node->key = k; node->right = node->left = NULL; return node; } int findRightLeavesSum(Node* root) { if (root == NULL) return 0; queue<pair<Node*, bool> > leftTreeNodes; leftTreeNodes.push({ root, 0 }); int sum = 0; while (!leftTreeNodes.empty()) { Node* temp = leftTreeNodes.front().first; bool is_left_child = leftTreeNodes.front().second; leftTreeNodes.pop(); if (!temp->left && !temp->right && is_left_child) sum = sum + temp->key; if (temp->left) { leftTreeNodes.push({ temp->left, 0 }); } if (temp->right) { leftTreeNodes.push({ temp->right, 1 }); } } return sum; } int main(){ Node *root = newNode(5); root->left= newNode(4); root->right = newNode(6); root->left->left = newNode(2); root->left->right = newNode(1); root->right->left = newNode(9); root->right->right= newNode(7); cout<<"The sum of right leaves of the tree is "<<findRightLeavesSum(root); return 0; } आउटपुट
The sum of right leaves of the tree is 8
