[C++] PAT 1004 Counting Leaves (30分)

Sample Input:

2 1 01 1 02

Sample Output:

0 1

题解：

给出一棵树，问每一层有多少个叶子节点，采用了DFS遍历

在#include <iostream> #include <vector> using namespace std; const int MAXN = 110; vector<int> T[MAXN];//T树结构 int n,depth[MAXN]={0};//n 节点数, depth[]深度 int maxDepth; void DFS(int root,int d){ if(d > maxDepth){ maxDepth = d; } if(T[root].empty()){ depth[d]++; return; } for(int i=0;i<T[root].size();i++){ DFS(T[root][i],d+1); } } int main(){ int m; cin >> n >> m; if(n == 0){ cout << 0; } else{ int root,root_n,temp_n; for(int i = 0;i< m;i++){ cin >> root >> root_n; for(int j = 0;j < root_n;j++){ cin >> temp_n; T[root].push_back(temp_n); } } DFS(1,0); for(int i=0;i<maxDepth;i++){ cout << depth[i] << " "; } cout << depth[maxDepth]; } system("pause"); return 0; }