题目链接：1004 Counting Leaves

思路

第一次见30分的题，被分数吓到了，没想到代码一次过，甚是喜悦！

因为知道根结点，选择孩子表保存树，本来还想会不会族系树会不会还有夫妻什么的，两个人同一个孩子，看来是没有，是一棵正经的树。为了满足题目要求，结点中保存层数。使用队列辅助下进行树的层次遍历，孩子入队时修改level值为父亲的level+1。出队时若孩子数为0，说明是叶结点，计数+1。队伍为空说明遍历完成，记录下树高。输出数高范围内各层的叶子数。

代码

#include <iostream> #include <vector> #include <queue> using namespace std; struct node{ int id; int level; int k = 0; vector<int> child; }node[100]; int main(){ int M, N, K, id, a, maxlevel = 0, leaf[100] = {0}; cin >> N >> M; for(int i = 0; i < M; i++){ cin >> id >> K; node[id].k = K; for(int j = 0; j < K; j++){ cin >> a; node[id].child.push_back(a); } } id = 1; node[id].level = 0; queue<int> Q; Q.push(id); while(!Q.empty()){ id = Q.front(); Q.pop(); if(node[id].k == 0) leaf[node[id].level]++; for(int i = 0; i < node[id].k; i++){ a = node[id].child[i]; node[a].level = node[id].level + 1; Q.push(a); } if(Q.empty()) maxlevel = node[id].level; } for(int i=0;i<=maxlevel;i++){ cout << leaf[i]; if(i!=maxlevel) cout << ' '; } }