ধরুন আমাদের একটি বাইনারি গাছ আছে, তার মূলের স্তর হল 1, এর সন্তানদের স্তর হল 2, এবং আরও অনেক কিছু৷ আমাদেরকে সবচেয়ে ছোট স্তর X খুঁজে বের করতে হবে যাতে X স্তরে নোডের সমস্ত মানের সমষ্টি ন্যূনতম হয়৷ তাই গাছটি যদি −
এর মত হয়
আউটপুট 2 হবে কারণ যোগফল 4 – 10 =-6, যা সর্বনিম্ন।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
স্তর :=1, যোগফল :=r এর মান, ansLevel :=স্তর, ansSum :=যোগফল
-
একটি সারি q সংজ্ঞায়িত করুন, q
-এ প্রদত্ত নোড r সন্নিবেশ করুন -
যখন q খালি নয়
-
ক্ষমতা:=q এর আকার
-
1 দ্বারা স্তর বাড়ান, যোগফল :=0
-
যখন ক্ষমতা 0
নয়-
নোড :=q থেকে সামনের নোড, q থেকে নোড মুছে দিন
-
যদি নোডের ডানটি বৈধ হয়, তাহলে sum :=sum + ডান নোডের মান, ডান সন্নিবেশ করুন
- q এ নোড করুন
-
যদি নোডের বাম অংশটি বৈধ হয়, তাহলে sum :=sum + বাম নোডের মান, q তে লেফটনোড ঢোকান
-
1 দ্বারা ক্ষমতা হ্রাস করুন
-
-
যদি ansSum
-
-
ফেরত আনলেভেল
আসুন আরও ভাল বোঝার জন্য নিম্নলিখিত বাস্তবায়ন দেখি—
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
class TreeNode{
public:
int val;
TreeNode *left, *right;
TreeNode(int data){
val = data;
left = NULL;
right = NULL;
}
};
class Solution {
public:
int solve(TreeNode* r) {
int level = 1, sum = r->val;
int ansLevel = level, ansSum = sum;
queue <TreeNode*> q;
q.push(r);
while(!q.empty()){
int capacity = q.size();
level++;
sum = 0;
while(capacity--){
TreeNode* node = q.front();
q.pop();
if(node->right){
sum += node->right->val;
q.push(node->right);
}
if(node->left){
sum += node->left->val;
q.push(node->left);
}
}
if(ansSum>sum){
ansSum = sum;
ansLevel = level;
}
}
return ansLevel;
}
};
main(){
TreeNode *root = new TreeNode(5);
root->left = new TreeNode(4);
root->right = new TreeNode(-10);
root->left->right = new TreeNode(-2);
root->right->left = new TreeNode(-7);
root->right->right = new TreeNode(15);
Solution ob;
cout <<ob.solve(root);
} ইনপুট
TreeNode *root = new TreeNode(5); root->left = new TreeNode(4); root->right = new TreeNode(-10); root->left->right = new TreeNode(-2); root->right->left = new TreeNode(-7); root->right->right = new TreeNode(15);
আউটপুট
2
