इस समस्या में, हमें एक ट्री दिया गया है। और हमें उन सभी स्तरों को प्रिंट करना है जिनमें सम संख्या में नोड्स और विषम संख्या में नोड्स हैं।
अवधारणा को बेहतर ढंग से समझने के लिए एक उदाहरण लेते हैं
आउटपुट -
विषम संख्या में नोड्स वाले स्तर: 1, 3, 4 सम संख्या में नोड्स वाले स्तर: 2
व्याख्या - पहले स्तर में केवल 1 तत्व है (विषम), दूसरा स्तर दो तत्वों को समाहित करता है (सम), तीसरा स्तर 3 तत्वों को समाहित करता है (विषम) और चौथा स्तर 1 तत्व को समाहित करता है (सम)।
अब, इस समस्या को हल करने के लिए। हमें प्रत्येक स्तर पर नोड्स की गिनती ढूंढनी होगी और तदनुसार सम-विषम स्तर प्रिंट करने होंगे।
हम समाधान खोजने के लिए निम्नलिखित चरणों का पालन करेंगे -
चरण 1 - height[node]=1+height[parent] का उपयोग करके हर स्तर के लिए खोज एल्गोरिदम चलाएं
चरण 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
