共计 1002 个字符，预计需要花费 3 分钟才能阅读完成。
还是数层数和数节点的问题，个人觉得用 BFS 比较好；当然用 DFS 也能做，具体的思路就是建立层数数组，深度遍历到 x 层的时候，如果是叶子节点就 leaf[x]++，如果不是就不管，继续跳过；代码片段可以这样：
void DFS(int index,int h){
max_h=max(h,max_h);
if(G[index].size()==0){
leaf[h]++;
return;
}
for(int i=0;i<G[index].size();i++){
DFS(G[index][i],h+1);
}
}
BFS 代码如下所示：
#include<iostream>
#include<stdlib.h>
#include<stdio.h>
#include<vector>
#include<queue>
using namespace std;
using std::vector;
using std::queue;
const int maxn=110;
int n,m;
int leaf[maxn]={0};// 每层 leaf 个数
vector<int> table[maxn];
int BFS(int x){
int layer=0;
queue<int>q;
q.push(x);
while(!q.empty()){
int num=0;
int length=q.size();
layer++;
for(int i=0;i<length;i++){
int id=q.front();
q.pop();
if(table[id].size()==0){
num++;
}
for(int j=0;j<table[id].size();j++){
q.push(table[id][j]);
}
}
leaf[layer]=num;
}
return layer;
}
int main(){
int root,l,num;
scanf(“%d%d”,&n,&m);
for(int i=0;i<m;i++){
scanf(“%d %d”,&root,&num);
for(int j=0;j<num;j++){
scanf(“%d”,&l);
table[root].push_back(l);
}
}
int layer=BFS(1);
for(int i=1;i<=layer;i++){
if(i==1)
printf(“%d”,leaf[i]);
else
printf(” %d”,leaf[i]);
}
system(“pause”);
return 0;
}
