C++ এ বাইনারি গাছের পাতা খুঁজুন

ধরুন আমাদের একটি বাইনারি গাছ আছে। আমরা সমস্ত পাতা সংগ্রহ করে সরিয়ে ফেলব এবং গাছটি খালি না হওয়া পর্যন্ত পুনরাবৃত্তি করব৷

সুতরাং, যদি ইনপুট মত হয়

তাহলে আউটপুট হবে [[4,5,3],[2],[1]]

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি মানচিত্র sz

  সংজ্ঞায়িত করুন

• একটি 2D অ্যারে ret সংজ্ঞায়িত করুন

• একটি ফাংশন সংজ্ঞায়িত করুন dfs(), এটি নোড নেবে,

• যদি নোড নাল হয়, তাহলে −

  • sz[নোডের ভ্যাল] :=1 + সর্বাধিক dfs (নোডের বাম) এবং dfs (নোডের ডানদিকে)

• যদি ret

  • একটি অ্যারের তাপমাত্রা সংজ্ঞায়িত করুন

  • ret-এর শেষে temp সন্নিবেশ করুন

• ret[sz[নোডের ভ্যাল] - 1]

  এর শেষে নোডের ভ্যাল সন্নিবেশ করান

• রিটার্ন sz[নোডের ভ্যাল]

• প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন -

• dfs(root)

• রিটার্ন রিটার্ন

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

#include  namespace ব্যবহার করে std;void print_vector(vector v){ cout <<"["; for(int i =0; i 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); প্রত্যাবর্তন }অন্য{ q.push(temp->বাম); } if(!temp->right){ if(val !=NULL) temp->right =new TreeNode(val); else temp->right =new TreeNode(0); প্রত্যাবর্তন }অন্য{ q.push(temp->ডান); } }}TreeNode *make_tree(vector sz; ভেক্টর <ভেক্টর  ret; int dfs(TreeNode* node){ if(!node) return 0; sz[node->val] =1 + max(dfs(node->left), dfs(নোড->ডান)); if(ret.size() val]){ ভেক্টর val] - 1].push_back(node->val); রিটার্ন sz[নোড->ভাল]; } ভেক্টর<ভেক্টর findLeaves(TreeNode* root) { dfs(root); রিটার্ন ret; }};প্রধান(){সমাধান ob; ভেক্টর 
ইনপুট
 
{1,2,3,4,5}
 
আউটপুট
 <প্রে>[[3, 5, 4, ],[2, ],[1, ],]