ধরা যাক একটি ইন্টিজার অ্যারে আছে। সেটির সব উপাদান ইউনিক। এই অ্যারে ওপর একটি সর্বোচ্চ ট্রি (maximum tree) নির্মাণের নিয়ম নিচের মতো −
রুট অ্যারেতে সর্বোচ্চ সংখ্যাটি ধারণ করবে।
বাম সাবট্রি হবে সর্বোচ্চ সংখ্যার বামপাশের সাবঅ্যারে থেকে নির্মিত সর্বোচ্চ ট্রি।
ডান সাবট্রি হবে সর্বোচ্চ সংখ্যার ডানপাশের সাবঅ্যারে থেকে নির্মিত সর্বোচ্চ ট্রি।
আমাদের সর্বোচ্চ বাইনারি ট্রি কনস্ট্রাক্ট করতে হবে। যদি ইনপুট হয়: [3,2,1,6,0,5], তবে আউটপুট হবে −
সমাধানের ধাপগুলো −
solve() নামে একটি মেথড সংজ্ঞা করব, যা লিস্ট, left এবং right মান নিবে। ফাংশনটি নিচেরভাবে কাজ করবে −
যদি left > right হয়, তবে null রিটার্ন করব
maxIndex := left এবং maxVal := nums[left]
i = left + 1 থেকে right পর্যন্ত
যদি maxVal < nums[i] হয়, তবে maxVal := nums[i], maxIndex := i
maxVal মান দিয়ে একটি নোড তৈরি করব
নোডের বাম := solve(nums, left, maxIndex - 1)
নোডের ডান := solve(nums, maxIndex + 1, right)
নোড রিটার্ন করব
solve মেথডটি মেইন সেকশন থেকে নিচেরভাবে কল হবে: solve(nums, 0, nums অ্যারের দৈর্ঘ্য - 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
