Cho cây, in các cấp độ (level) có số nút chẵn và lẻ.
Ví dụ cây:
Levels with odd number of nodes: 1, 3, 4 Levels with even number of nodes: 2
Giải pháp: DFS tính độ cao (level) mỗi nút. Đếm số nút mỗi cấp độ. In cấp độ chẵn/lẻ.
Chương trình minh họa
#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 << "Các cấp độ có số nút lẻ: ";
for (int i = 1; i <= maxLevel; i++)
if (mark[i] % 2) cout << i << " ";
cout << "\nCác cấp độ có số nút chẵn: ";
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;
}
Kết quả
Các cấp độ có số nút lẻ: 1 3 4 Các cấp độ có số nút chẵn: 2