একটি বাইনারি ট্রি দেওয়া আছে। আমাদের কাজ হলো সব লীফ নোডগুলো সংগ্রহ করে মুছে ফেলা, তারপর আবার নতুন লীফ নোডগুলো সংগ্রহ করা — এভাবে ট্রি খালি না হওয়া পর্যন্ত চলাতে হবে। প্রতিটি ধাপে সংগৃহীত লীফ নোডগুলো একটি সাব-অ্যারে হিসেবে রাখতে হবে।
উদাহরণ
আউটপুট: [[4,5,3],[2],[1]]
ব্যাখ্যা: প্রথমে লীফ নোডগুলো ৪, ৫, ৩; তাদের মুছে ফেলার পর লীফ হয় ২; তারপর ১।
সমাধানের পদ্ধতি (DFS + Height Calculation)
প্রতিটি নোডের "উচ্চতা" (height) বের করলে সহজে সমাধান করা যায়। লীফ নোডদের উচ্চতা ১, তাদের প্যারেন্টদের উচ্চতা ২, ইত্যাদি। একই উচ্চতায় থাকা নোডগুলো একই লেভেলে মুছে যাবে।
- একটি ম্যাপ
sz(নোড ভ্যালু → উচ্চতা) এবং ২D ভেক্টরretঘোষণা করুন। dfs(node)ফাংশন লিখুন:- যদি নোড নাল হয়, তবে ০ রিটার্ন করুন।
- বাম ও ডান সাবট্রির উচ্চতা বের করুন, তাদের ম্যাক্সিমাম + ১ = বর্তমান নোডের উচ্চতা।
sz[node->val] = heightসেট করুন।- যদি
ret.size() < heightহয়, তবেret-তে নতুন ভেক্টর যোগ করুন। ret[height-1]-এ নোডের ভ্যালু পুশ করুন।- উচ্চতা রিটার্ন করুন।
- মেইন ফাংশনে
dfs(root)কল করেretরিটার্ন করুন।
C++ কোড উদাহরণ
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<int>> v) {
cout << "[";
for(int i = 0; i < v.size(); i++) {
cout << "[";
for(int j = 0; j < v[i].size(); j++)
cout << v[i][j] << ", ";
cout << "],";
}
cout << "]" << endl;
}
class TreeNode {
public:
int val;
TreeNode *left, *right;
TreeNode(int data) {
val = data;
left = 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:
unordered_map<int, int> sz;
vector<vector<int>> ret;
int dfs(TreeNode* node) {
if(!node) return 0;
sz[node->val] = 1 + max(dfs(node->left), dfs(node->right));
if(ret.size() < sz[node->val]) {
vector<int> temp;
ret.push_back(temp);
}
ret[sz[node->val] - 1].push_back(node->val);
return sz[node->val];
}
vector<vector<int>> findLeaves(TreeNode* root) {
dfs(root);
return ret;
}
};
int main() {
Solution ob;
vector<int> v = {1,2,3,4,5};
TreeNode *root = make_tree(v);
print_vector(ob.findLeaves(root));
return 0;
}
ইনপুট
{1,2,3,4,5}
আউটপুট
[[3, 5, 4, ],[2, ],[1, ],]
