ধরুন আমাদের একটি পূর্ণসংখ্যা অ্যারে আছে। যে অ্যারের সব উপাদান অনন্য. এই অ্যারেতে সর্বাধিক ট্রি বিল্ডিং অনুসরণ −
হিসাবে সংজ্ঞায়িত করা হয়েছে-
রুট অ্যারেতে সর্বাধিক সংখ্যা ধরে রাখবে।
-
বাম সাবট্রি হল সর্বোচ্চ সংখ্যা দ্বারা ভাগ করে সাবয়ারের বাম দিক থেকে নির্মিত সর্বোচ্চ গাছ।
-
ডান সাবট্রি হল সর্বোচ্চ সংখ্যা দ্বারা ভাগ করে সাবয়ারের ডান দিক থেকে নির্মিত সর্বোচ্চ গাছ।
আমাদের সর্বোচ্চ বাইনারি গাছ তৈরি করতে হবে। সুতরাং যদি ইনপুটটি এরকম হয়:[3,2,1,6,0,5], তাহলে আউটপুট হবে −
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
সমাধান() নামক একটি পদ্ধতি নির্ধারণ করুন, এটি তালিকা এবং বাম এবং ডান মান গ্রহণ করবে। ফাংশনটি নিম্নরূপ কাজ করবে -
-
যদি বাম> ডান, তারপর শূন্য ফেরত
-
maxIndex :=left এবং maxVal :=সংখ্যা[বাম]
-
আমি বাম + 1 থেকে ডানে
পরিসরে-
যদি maxVal
-
-
মান maxVal
সহ একটি নোড সংজ্ঞায়িত করুন -
নোডের বাম :=সমাধান (সংখ্যা, বাম, সর্বোচ্চ সূচক - 1)
-
নোডের ডানদিকে :=সমাধান (সংখ্যা, ম্যাক্স ইনডেক্স + 1, ডান)
-
রিটার্ন নোড
-
সমাধান পদ্ধতিটি প্রধান বিভাগ থেকে বলা হবে যেমন:সমাধান(সংখ্যা, 0, সংখ্যা অ্যারের দৈর্ঘ্য - 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;
}
void inord(TreeNode *root){
if(root != NULL){
inord(root->left);
cout << root->val << " ";
inord(root->right);
}
}
class Solution {
public:
TreeNode* solve(vector <int>& nums, int left, int right){
if(left>right)return NULL;
int maxIndex = left;
int maxVal = nums[left];
for(int i = left + 1; i <= right; i++){
if(maxVal < nums[i]){
maxVal = nums[i];
maxIndex = i;
}
}
TreeNode* node = new TreeNode(maxVal);
node->left = solve(nums, left, maxIndex - 1);
node->right = solve(nums, maxIndex + 1, right);
return node;
}
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
return solve(nums, 0, nums.size() - 1);
}
};
main(){
vector<int> v = {4,3,2,7,1,6};
Solution ob;
inord(ob.constructMaximumBinaryTree(v));
} ইনপুট
[3,2,1,6,0,5]
আউটপুট
4 3 2 7 1 6
