ধরুন আমাদের একটি বাইনারি ট্রি আছে, প্রদত্ত গাছের সর্বোচ্চ প্রস্থ পেতে আমাদের একটি ফাংশন সংজ্ঞায়িত করতে হবে। এখানে একটি গাছের প্রস্থ হল সব স্তরের মধ্যে সর্বাধিক প্রস্থ। আমরা বিবেচনা করব বাইনারি গাছের গঠন সম্পূর্ণ বাইনারি গাছের মতো, কিন্তু কিছু নোড শূন্য। একটি স্তরের প্রস্থ আসলে শেষ-নোডগুলির মধ্যে দৈর্ঘ্য (লেভেলের সবচেয়ে বাম এবং ডানদিকে সবচেয়ে নন-নাল নোড, যেখানে শেষ-নোডের মধ্যে নাল নোডগুলিও দৈর্ঘ্য গণনার জন্য গণনা করা হয়)। তাই গাছটি যদি −
এর মত হয়
তারপর সর্বাধিক প্রস্থ 4, কারণ শেষ স্তরের নোডগুলি হল [5,3,null,9]
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
উত্তর :=1, আকার :=0
-
একটি ডবল শেষ সারি q সংজ্ঞায়িত করুন যেখানে আমরা (নোড, মান) জোড়া সংরক্ষণ করব।
-
q
-এ (মূল, 1) সন্নিবেশ করান -
যখন q খালি নয়
-
আকার :=q এর আকার
-
একটি (নোড, মান) জোড়া curr
সংজ্ঞায়িত করুন -
যদি আকার 1 হয়, তাহলে (সামনের উপাদানটির নোড, 1) q তে, q থেকে উপাদান মুছুন
-
যখন আকার 0
নয়-
curr :=q এর সামনের উপাদান, q থেকে সামনের উপাদানটি মুছে দিন
-
যদি curr নোডের বাম অংশ শূন্য না হয়, তাহলে
-
তৈরি করুন (বর্তমান নোডের বামে, curr এর 2*মান) এবং q
-এ সন্নিবেশ করুন
-
-
যদি curr নোডের ডানদিকে শূন্য না হয়, তাহলে
-
তৈরি করুন (বর্তমান নোডের ডানদিকে, curr + 1 এর 2*মান) এবং q এ সন্নিবেশ করুন
-
-
যদি q> 1 এর আকার হয়, তাহলে
-
ans :=উত্তরের সর্বোচ্চ, q এর শেষ উপাদানটির মান – q + 1 এর প্রথম উপাদানের মান
-
-
আকার:=আকার – 1
-
-
-
উত্তর ফেরত দিন
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
class TreeNode{
public:
int val;
TreeNode *left, *right;
TreeNode(int data){
val = data;
left = NULL;
right = NULL;
}
};
void insert(TreeNode **root, int val){
queue<TreeNode*> q;
q.push(*root);
while(q.size()){
TreeNode *temp = q.front();
q.pop();
if(!temp->left){
if(val != NULL)
temp->left = new TreeNode(val);
else
temp->left = new TreeNode(0);
return;
}else{
q.push(temp->left);
}
if(!temp->right){
if(val != NULL)
temp->right = new TreeNode(val);
else
temp->right = new TreeNode(0);
return;
}else{
q.push(temp->right);
}
}
}
TreeNode *make_tree(vector<int> v){
TreeNode *root = new TreeNode(v[0]);
for(int i = 1; i<v.size(); i++){
insert(&root, v[i]);
}
return root;
}
class Solution {
public:
int widthOfBinaryTree(TreeNode* root) {
int ans = 0;
deque < pair <TreeNode*, int> > q;
q.push_back({root,1});
ans = 1;
int size;
while(!q.empty()){
size = q.size();
pair <TreeNode*, int> curr;
if(size == 1){
q.push_back({q.front().first, 1});
q.pop_front();
}
while(size--){
curr = q.front();
q.pop_front();
if(curr.first->left){
q.push_back({curr.first->left, 2 * curr.second});
}
if(curr.first->right){
q.push_back({curr.first->right, 2 * curr.second + 1});
}
}
if(q.size() > 1)
ans = max(ans, q.back().second - q.front().second + 1);
}
return ans;
}
};
main(){
vector<int> v = {1,3,2,5,3,NULL,9};
TreeNode *root = make_tree(v);
Solution ob;
cout << (ob.widthOfBinaryTree(root));
} ইনপুট
[1,3,2,5,3,null,9]
আউটপুট
4
