ধরি আমাদের একটি ম্যাক্সিমাম ট্রির রুট নোড আছে: ম্যাক্সিমাম ট্রি হল এমন একটি ট্রি যেখানে প্রতিটি নোডের ভ্যালু তার সাবট্রির যেকোনো অন্য ভ্যালু থেকে বড়। ধরি আমাদের একটি construct() মেথড আছে। এটি একটি লিস্ট A থেকে রুট কনস্ট্রাক্ট করতে পারে। construct() মেথড নিচের মত:
যদি লিস্ট A খালি হয়, তবে null রিটার্ন করুন।
অন্যথায়, A[i] হোক লিস্ট A-র সবচেয়ে বড় এলিমেন্ট। তারপর A[i] ভ্যালু দিয়ে একটি রুট নোড তৈরি করুন।
রুটের লেফট চাইল্ড হবে construct([A[0], A[1], ..., A[i-1]])
রুটের রাইট চাইল্ড হবে construct([A[i+1], A[i+2], ..., A[n-1]]) [n হল A-এর দৈর্ঘ্য]
রুট রিটার্ন করুন।
নোট করুন যে আমাদের A সরাসরি দেওয়া হয়নি, শুধু একটি রুট নোড root = construct(A) দেওয়া আছে। এখন ধরি B হল A-এর একটি কপি যাতে val ভ্যালু অ্যাড করা হয়েছে। গ্যারান্টি দেওয়া আছে যে B-তে ইউনিক ভ্যালু আছে। আমাদের construct(B) কনস্ট্রাক্ট করতে হবে। যদি val 5 হয় এবং ইনপুট ট্রি নিচের মত হয়:
আউটপুট ট্রি হবে নিচের মত:
এটি সমাধান করার জন্য নিচের ধাপগুলো অনুসরণ করব:
একটি রিকার্সিভ মেথড solve() ডিফাইন করুন। এটি root এবং val নিবে।
যদি ট্রি খালি হয়, তবে val ভ্যালু দিয়ে একটি নতুন নোড তৈরি করুন, এবং সেই নোড রিটার্ন করুন
যদি root-এর ভ্যালু < val হয়, তবে
temp := val ভ্যালু দিয়ে একটি নতুন নোড
temp-এর left := root
temp রিটার্ন করুন
root->right := solve(root->right, val)
root রিটার্ন করুন
নিচের ইমপ্লিমেন্টেশনটি দেখুন ভালো বোঝার জন্য:
উদাহরণ
#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 tree_level_trav(TreeNode* root) {
if (root == NULL) return;
cout << "[";
queue<TreeNode *> q;
TreeNode *curr;
q.push(root);
q.push(NULL);
while (q.size() > 1) {
curr = q.front();
q.pop();
if (curr == NULL) {
q.push(NULL);
} else {
if(curr->left) q.push(curr->left);
if(curr->right) q.push(curr->right);
if(curr == NULL || curr->val == 0) {
cout << "null" << ", ";
} else {
cout << curr->val << ", ";
}
}
}
cout << "]" << endl;
}
class Solution {
public:
TreeNode* insertIntoMaxTree(TreeNode* root, int val) {
if(!root) return new TreeNode(val);
if(root->val < val) {
TreeNode* temp = new TreeNode(val);
temp->left = root;
return temp;
}
root->right = insertIntoMaxTree(root->right, val);
return root;
}
};
int main() {
vector<int> v = {4,1,3,NULL,NULL,2};
TreeNode *root = make_tree(v);
Solution ob;
tree_level_trav(ob.insertIntoMaxTree(root, 5));
}
ইনপুট
[4,1,3,null,null,2] 5
আউটপুট
[5, 4, 1, 3, null, null, 2, ]
