একটি বাইনারি ট্রি দেওয়া আছে। তার মিনিমাম ডেপথ (রুট থেকে নিকটতম লিফ নোড পর্যন্ত নোড সংখ্যা) বের করুন।
উদাহরণ: ট্রি [3,9,20,null,null,15,7] -> আউটপুট ২।
সমাধানের ধাপসমূহ
- বিএফএস (লেভেল অর্ডার ট্রভার্সাল) ব্যবহার করুন।
- কিউতে রুট রাখুন, level = 0।
- প্রতিটি লেভেলের জন্য: যদি কোনো নোডের বাম ও ডান দুটোই null হয়, level রিটার্ন করুন।
- অন্যথায় সন্তানগুলো কিউতে পুশ করুন।
C++ কোড উদাহরণ
#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;
}
class Solution {
public:
int minDepth(TreeNode* root) {
vector<TreeNode*> aa; aa.push_back(root);
vector<TreeNode*> ak;
int level = 0;
if (root == NULL || root->val == 0) return 0;
while (aa.size() != 0) {
ak.clear(); level++;
for (TreeNode* a : aa) {
if ((a->left == NULL || a->left->val == 0) && (a->right == NULL || a->right->val == 0))
return level;
if (a->left != NULL) ak.push_back(a->left);
if (a->right != NULL) ak.push_back(a->right);
}
aa = ak;
}
return 0;
}
};
int main() {
Solution ob;
vector<int> v = {3,9,20,NULL,NULL,15,7};
TreeNode *root = make_tree(v);
cout << ob.minDepth(root);
return 0;
}
ইনপুট
{3,9,20,NULL,NULL,15,7}
আউটপুট
2
