ধরা যাক একটি বাইনারি ট্রি আছে, আমরা ট্রির প্রতিটি লেভেলের সর্বোচ্চ উপাদান বের করব। যদি ট্রি নিচের মতো হয় −
তবে আউটপুট হবে [3,5,8]
সমাধানের ধাপগুলো −
ans নামক একটি অ্যারে সংজ্ঞা করব
solve() নামে একটি রিকারসিভ ফাংশন সংজ্ঞা করব, যা ট্রি নোড এবং লেভেল নিবে, লেভেল প্রাথমিকভাবে 0। এই মেথডটি নিচেরভাবে কাজ করবে −
যদি নোড null হয়, তবে রিটার্ন করব
যদি level = ans-এর সাইজ হয়, তবে নোডের মান ans-এ ইনসার্ট করব, অন্যথায় ans[level] := ans[level] এবং নোডের মানের ম্যাক্সিমাম
solve(নোডের বাম সাবট্রি, level + 1) কল করব
solve(নোডের ডান সাবট্রি, level + 1) কল করব
মেইন মেথড থেকে solve() কল করব root প্যারামিটার দিয়ে, এবং level = 0
তারপর ans রিটার্ন করব
নিচের ইমপ্লিমেন্টেশন দেখুন −
উদাহরণ
#include <bits/stdc++.h> using namespace std; void print_vector(vector<auto> v){ cout << "["; for(int i = 0; i<v.size(); i++){ cout << v[i] << ", "; } cout << "]"<<endl; } 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: vector <int> ans; void solve(TreeNode* node, int level = 0){ if(!node)return; if(level == ans.size()){ ans.push_back(node->val); } else { ans[level] = max(ans[level], node->val); } solve(node->left, level + 1); solve(node->right, level + 1); } vector<int> largestValues(TreeNode* root) { solve(root); return ans; } }; main(){ vector<int> v = {1,3,2,5,3,NULL,9}; TreeNode *tree = make_tree(v); Solution ob; print_vector(ob.largestValues(tree)); }
ইনপুট
[1,3,2,5,3,null,9]
আউটপুট
[1, 3, 9, ]
