ধরুন আমাদের একটি বাইনারি গাছ আছে; আমাদের সেই গাছের ন্যূনতম গভীরতা খুঁজে বের করতে হবে। আমরা জানি যে ন্যূনতম গভীরতা হল রুট নোড থেকে নীচের পাতার নোড পর্যন্ত সংক্ষিপ্ততম পথ বরাবর নোডের সংখ্যা৷
সুতরাং, যদি ইনপুট মত হয়
তাহলে আউটপুট হবে 2
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
ট্রি নোডের একটি অ্যারে সংজ্ঞায়িত করুন
-
aa
এর শেষে রুট সন্নিবেশ করান -
ট্রি নোডের আরেকটি অ্যারে সংজ্ঞায়িত করুন
-
স্তর :=0
-
যদি মূল শূন্য হয়, তাহলে −
-
রিটার্ন 0
-
-
যখন aa-এর আকার 0 এর সমান নয়, −
করুন-
অ্যারে সাফ করুন ak
-
(1 দ্বারা স্তর বাড়ান)
-
সমস্ত নোডের জন্য a in aa −
-
যদি (a এর বাম নাল হয়) এবং (a এর ডান নাল হয়), তাহলে −
-
রিটার্ন লেভেল
-
লুপ থেকে বেরিয়ে আসুন
-
-
যদি a এর বাম শূন্য না হয়, তাহলে −
-
ak
-এর শেষে a-এর বাম দিকে ঢোকান
-
-
যদি a-এর অধিকার শূন্য না হয়, তাহলে −
-
ak
-এর শেষে a-এর ডানদিকে সন্নিবেশ করুন
-
-
-
aa :=ak
-
-
রিটার্ন 0
উদাহরণ
আরো ভালোভাবে বোঝার জন্য নিচের বাস্তবায়নটি দেখি -
#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; break; } if (a->left != NULL) { ak.push_back(a->left); } if (a->right != NULL) { ak.push_back(a->right); } } aa = ak; } return 0; } }; main(){ Solution ob; vector<int&g; v = {3,9,20,NULL,NULL,15,7}; TreeNode *root = make_tree(v); cout << (ob.minDepth(root)); }
ইনপুট
{3,9,20,NULL,NULL,15,7}
আউটপুট
2