এই সমস্যায়, আমাদের একটি গাছ দেওয়া হয়। এবং আমাদের সমস্ত স্তরগুলিকে নোডের জোড় সংখ্যা এবং বিজোড় সংখ্যক নোড সহ প্রিন্ট করতে হবে৷
ধারণাটি আরও ভালভাবে বোঝার জন্য একটি উদাহরণ নেওয়া যাক
আউটপুট -
Levels with odd number of nodes: 1, 3, 4 Levels with even number of nodes: 2
ব্যাখ্যা − প্রথম স্তরে মাত্র 1টি উপাদান (বিজোড়), দ্বিতীয় স্তরে দুটি উপাদান (জোড়), তৃতীয় স্তরে 3টি উপাদান (বিজোড়) এবং চতুর্থ স্তরে 1টি উপাদান (জোড়) রয়েছে৷
এখন, এই সমস্যা সমাধানের জন্য. আমাদের প্রতিটি স্তরে নোডের সংখ্যা খুঁজে বের করতে হবে এবং সেই অনুযায়ী জোড়-বিজোড় স্তরগুলি প্রিন্ট করতে হবে৷
সমাধান খুঁজে পেতে আমরা নিম্নলিখিত পদক্ষেপগুলি অনুসরণ করব -
ধাপ 1 − উচ্চতা[নোড]=1+উচ্চতা[অভিভাবক]
ব্যবহার করে প্রতিটি স্তরের জন্য অনুসন্ধান অ্যালগরিদম চালানধাপ 2 − প্রতিটি স্তরের জন্য সেই স্তরে নোডের সংখ্যা সংরক্ষণ করুন৷
৷ধাপ 3 − উপাদান সম্বলিত অ্যারের উপর পুনরাবৃত্তি করুন এবং জোড় ও বিজোড় স্তরে মুদ্রণ করুন।
উদাহরণ
#include <bits/stdc++.h> using namespace std; void traversal(int node, int parent, int height[], int vis[], vector<int> tree[]){ height[node] = 1 + height[parent]; vis[node] = 1; for (auto it : tree[node]) { if (!vis[it]) { traversal(it, node, height, vis, tree); } } } void insert(int x, int y, vector<int> tree[]){ tree[x].push_back(y); tree[y].push_back(x); } void evenOddLevels(int N, int vis[], int height[]){ int mark[N + 1]; memset(mark, 0, sizeof mark); int maxLevel = 0; for (int i = 1; i <= N; i++) { if (vis[i]) mark[height[i]]++; maxLevel = max(height[i], maxLevel); } cout << "The levels with odd number of nodes are: "; for (int i = 1; i <= maxLevel; i++) { if (mark[i] % 2) cout << i << " "; } cout << "\nThe levels with even number of nodes are: "; for (int i = 1; i <= maxLevel; i++) { if (mark[i] % 2 == 0) cout << i << " "; } } int main(){ const int N = 9; vector<int> tree[N + 1]; insert(1, 2, tree); insert(1, 3, tree); insert(2, 4, tree); insert(2, 5, tree); insert(5, 7, tree); insert(5, 8, tree); insert(3, 6, tree); insert(6, 9, tree); int height[N + 1]; int vis[N + 1] = { 0 }; height[0] = 0; traversal(1, 0, height, vis, tree); evenOddLevels(N, vis, height); return 0; }
আউটপুট
The levels with odd number of nodes are: 1 3 4 The levels with even number of nodes are: 2