मान लीजिए कि हमारे पास एक पूर्णांक सरणी है। उस सरणी के सभी तत्व अद्वितीय हैं। इस सरणी पर अधिकतम वृक्ष निर्माण को निम्नानुसार परिभाषित किया गया है -
-
जड़ सरणी में अधिकतम संख्या धारण करेगा।
-
लेफ्ट सबट्री सबएरे के बायीं ओर से निर्मित अधिकतम ट्री है जिसे अधिकतम संख्या से विभाजित किया जाता है।
-
दायां उपप्रकार अधिकतम संख्या से विभाजित उप-सरणी के दाईं ओर से निर्मित अधिकतम वृक्ष है।
हमें अधिकतम बाइनरी ट्री बनाना है। तो अगर इनपुट इस तरह है:[3,2,1,6,0,5], तो आउटपुट होगा -
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
हल () नामक एक विधि को परिभाषित करें, यह सूची और बाएँ और दाएँ मान लेगा। फ़ंक्शन निम्नानुसार काम करेगा -
-
अगर बाएँ> दाएँ, तो वापस अशक्त हो जाएँ
-
maxIndex:=बाएँ और maxVal:=nums[left]
-
क्योंकि मैं बाएँ + 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