মনে করুন একটি বাইনারি ট্রি `root`-এ রুটেড আছে, প্রতিটি নোডের ডেপথ হলো রুট থেকে সেটির শর্টেস্ট দূরত্ব। এখানে একটি নোড "গভীরতম" হবে যদি সেটির ডেপথ পুরো ট্রিতে যেকোনো নোডের ডেপথ থেকে বড় বা সমান হয়। একটি নোডের সাবট্রি হলো সেটি নিজে, এবং তার সব ডিসেন্ডেন্টের সেট। আমাদের সেই নোড খুঁজে বের করতে হবে যেটির ডেপথ সর্বোচ্চ এবং যেটির সাবট্রিতে সব গভীরতম নোডগুলো থাকে। যদি ট্রি নিচের মোতাবিক হয় -
তবে গভীরতম সাবট্রি হবে -
এটি সমাধান করতে আমরা নিচের ধাপগুলো অনুসরণ করব -
- `solve()` নামক একটি মেথড সংজ্ঞায়িত করুন, এটি `root` ইনপুট নেবে
- যদি `root` null হয়, তবে `(null, 0)` রিটার্ন করুন
- `l := solve(root`-এর বাম), `r := solve(root`-এর ডান)
- যদি `l`-এর সেকেন্ড ভ্যালু `r`-এর সেকেন্ড ভ্যালুর চেয়ে বড় হয়, তবে `(l.first, 1 + l.second)` পেয়ার রিটার্ন করুন
- অন্যথায় যখন `l`-এর সেকেন্ড ভ্যালু `r`-এর সেকেন্ড ভ্যালুর চেয়ে ছোট হয়, তবে `(r.first, 1 + r.second)` পেয়ার রিটার্ন করুন
- `(root, l.second + 1)` পেয়ার রিটার্ন করুন
- মেইন মেথড থেকে `solve(root)` কল করুন, এবং এর সেকেন্ড ভ্যালু রিটার্ন করুন
উদাহরণ (C++)
বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশনটি দেখুন -
#include <bits/stdc++.h> using namespace std; 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; } void tree_level_trav(TreeNode*root){ if (root == NULL) return; cout << "["; queue<TreeNode *> q; TreeNode *curr; q.push(root); q.push(NULL); while (q.size() > 1) { curr = q.front(); q.pop(); if (curr == NULL){ q.push(NULL); } else { if(curr->left) q.push(curr->left); if(curr->right) q.push(curr->right); if(curr->val == 0 || curr == NULL){ cout << "null" << ", "; } else { cout << curr->val << ", "; } } } cout << "]"<<endl; } class Solution { public: pair <TreeNode*, int> solve(TreeNode* root){ if(!root || root->val == 0) return {NULL, 0}; pair <TreeNode*, int> L = solve(root->left); pair <TreeNode*, int> R = solve(root->right); if(L.second > R.second)return {L.first, L.second + 1}; else if(L.second < R.second) return {R.first, R.second + 1}; return {root, L.second + 1}; } TreeNode* subtreeWithAllDeepest(TreeNode* root) { return solve(root).first; } }; main(){ vector<int> v = {3,5,1,6,2,0,8,NULL,NULL,7,4}; TreeNode *root = make_tree(v); Solution ob; tree_level_trav(ob.subtreeWithAllDeepest(root)) ; }ইনপুট
{3,5,1,6,2,0,8,NULL,NULL,7,4}আউটপুট
[2,7,4]
