এই সমস্যায়, আমরা একটি বাইনারি গাছ দেওয়া হয়. আমাদের কাজ হল একটি প্রদত্ত বাইনারি ট্রিতে সমস্ত বাম ডানের যোগফল খুঁজে বের করা .
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট:
আউটপুট:8
ব্যাখ্যা −
All leaf nodes of the tree are : 1, 8 Sum = 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
