ধারণা
একটি প্রদত্ত বাইনারি গাছের সম্মানে, এটির জন্য নিম্নলিখিত মানটি ফেরত দিন৷
-
প্রতিটি স্তরের সাপেক্ষে, এই স্তরে পাতা থাকলে সমস্ত পাতার যোগফল গণনা করুন। অন্যথায় এটি উপেক্ষা করুন।
-
সমস্ত রাশির গুণন গণনা করুন এবং ফেরত দিন।
ইনপুট
Root of following tree 3 / \ 8 6 \ 10
আউটপুট
80
প্রথম স্তরের পাতা নেই। দ্বিতীয় স্তরে একটি পাতা 8 এবং তৃতীয় স্তরে একটি পাতা 10 রয়েছে৷ সুতরাং ফলাফল 8*10 =80
ইনপুট
Root of following tree 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).
আবার একটি দক্ষ সমাধানের ক্ষেত্রে, আমরা সারি ভিত্তিক লেভেল অর্ডার ট্রাভার্সাল বাস্তবায়ন করি। এখানে, ট্রাভার্সাল করার সময়, আমরা আলাদাভাবে সমস্ত বিভিন্ন স্তর প্রক্রিয়া করি। প্রতিটি প্রক্রিয়াকৃত স্তরের জন্য, এটির একটি পাতা আছে কিনা তা যাচাই করুন। এই ক্ষেত্রে, যদি এটি থাকে তাহলে লিফ নোডের যোগফল গণনা করুন। শেষ পর্যন্ত, সমস্ত রাশির পণ্য ফেরত দিন।
উদাহরণ
/* Iterative C++ program to find sum of data of all leaves
of a binary tree on same level and then multiply sums
obtained of all levels. */
#include <bits/stdc++.h>
using namespace std;
// Shows a Binary Tree Node
struct Node1 {
int data1;
struct Node1 *left1, *right1;
};
// Shows helper function to check if a Node is leaf of tree
bool isLeaf(Node1* root1){
return (!root1->left1 && !root1->right1);
}
/* Compute sum of all leaf Nodes at each level and returns
multiplication of sums */
int sumAndMultiplyLevelData(Node1* root1){
// Here tree is empty
if (!root1)
return 0;
int mul1 = 1; /* Used To store result */
// Build an empty queue for level order tarversal
queue<Node1*> q1;
// Used to Enqueue Root and initialize height
q1.push(root1);
// Perform level order traversal of tree
while (1) {
// NodeCount1 (queue size) indicates number of Nodes
// at current lelvel.
int NodeCount1 = q1.size();
// Now if there are no Nodes at current level, we are done
if (NodeCount1 == 0)
break;
// Used to initialize leaf sum for current level
int levelSum1 = 0;
// Shows a boolean variable to indicate if found a leaf
// Node at current level or not
bool leafFound1 = false;
// Used to Dequeue all Nodes of current level and Enqueue
all
// Nodes of next level
while (NodeCount1 > 0) {
// Process next Node of current level
Node1* Node1 = q1.front();
/* Now if Node is a leaf, update sum at the level */
if (isLeaf(Node1)) {
leafFound1 = true;
levelSum1 += Node1->data1;
}
q1.pop();
// Add children of Node
if (Node1->left1 != NULL)
q1.push(Node1->left1);
if (Node1->right1 != NULL)
q1.push(Node1->right1);
NodeCount1--;
}
// Now if we found at least one leaf, we multiply
// result with level sum.
if (leafFound1)
mul1 *= levelSum1;
}
return mul1; // Here, return result
}
//Shows utility function to create a new tree Node
Node1* newNode(int data1){
Node1* temp1 = new Node1;
temp1->data1 = data1;
temp1->left1 = temp1->right1 = NULL;
return temp1;
}
// Driver program to test above functions
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 << "Final product value = "
<< sumAndMultiplyLevelData(root1) <<endl;
return 0;
} আউটপুট
Final product value = 270
