इस समस्या में हमें एक बाइनरी ट्री दिया जाता है। हमारा काम है किसी दिए गए बाइनरी ट्री में सभी बाईं पत्तियों का योग ज्ञात करना ।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट:
आउटपुट:11
स्पष्टीकरण -
All leaf nodes of the tree are : 2, 9 Sum = 2 + 9 = 11
समाधान दृष्टिकोण
समस्या का एक सरल समाधान पेड़ को जड़ से पत्ती तक ले जाना है। यदि कोई नोड एक लेफ्ट लीफ नोड है, तो इसे योग में जोड़ें। जब पूरे पेड़ का पता लगाया जाता है। प्रिंट योग।
उदाहरण
हमारे समाधान की कार्यप्रणाली को दर्शाने के लिए कार्यक्रम
#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 findLeftLeavesSum(Node *root){
int sum = 0;
if (root != NULL){
if (isLeafNode(root->left))
sum += root->left->key;
else
sum += findLeftLeavesSum(root->left);
sum += findLeftLeavesSum(root->right);
}
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 left leaves of the tree is "<<findLeftLeavesSum(root);
return 0;
} आउटपुट
The sum of left leaves of the tree is 11
Iteration का उपयोग करने वाला दूसरा तरीका
हम पहले पेड़ पर गहराई से खोज ट्रैवर्सल करेंगे, और फिर जांचें कि क्या वर्तमान नोड एक बायां पत्ता है। यदि हाँ, तो इसके मान को योग में जोड़ें, अन्यथा, छोड़ दें। अंत में, योग प्रिंट करें।
उदाहरण
हमारे समाधान की कार्यप्रणाली को दर्शाने के लिए कार्यक्रम
#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 findLeftLeavesSum(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->left != NULL){
treeNodes.push(currentNode->left);
if(currentNode->left->left == NULL &&
currentNode->left->right == NULL){
sum += currentNode->left->key ;
}
}
if (currentNode->right != NULL)
treeNodes.push(currentNode->right);
}
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 left leaves of the tree is "<<findLeftLeavesSum(root);
return 0;
} आउटपुट
The sum of left leaves of the tree is 11
दृष्टिकोण 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 findLeftLeavesSum(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, 1 });
}
if (temp->right) {
leftTreeNodes.push({ temp->right, 0 });
}
}
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 left leaves of the tree is "<<findLeftLeavesSum(root);
return 0;
} आउटपुट
The sum of left leaves of the tree is 11