1004 Counting Leaves (30 分)

再次更新：第二次刷pat，又用到了别的方法，真是条条大路通罗马，这次用层序遍历。欢乐呀。

#include<iostream> #include<vector> #include<queue> using namespace std; int level[100] = { 0 }, n, m, maxD = 0; vector<vector<int>>tree; vector<int>ans; void f(int start) { queue < int>q; int last = start; int cnt = 0; q.push(start); while (!q.empty()) { int temp = q.front(); if (tree[temp].size() == 0)cnt++; for (int i = 0; i < tree[temp].size(); i++)q.push(tree[temp][i]); if (temp == last) { last = q.back(); ans.push_back(cnt); cnt = 0; } q.pop(); } } int main() { cin >> n >> m; tree.resize(100); for (int i = 0; i < m; i++) { int id, num; cin >> id >> num; for (int j = 0; j < num; j++) { int d; cin >> d; tree[id].push_back(d); } } f(1); for (int i = 0; i < ans.size(); i++) { cout << ans[i]; if (i == ans.size() - 1)cout << endl; else cout << " "; } return 0; }

更新，最近做了几道树的题，回顾这一题，发现用dfs更直观简单

#include<vector> #include<iostream> using namespace std; #define maxn 110 struct node{ //树的静态存储 vector<int>children; }t[maxn]; int n,m; int ithLevel[maxn];//保存第i层上无孩子节点的数目 int maxLevel=-1; //保存最大层数，便于输出 void dfs(int root,int depth){ if(t[root].children.size()==0){ if(depth>maxLevel)maxLevel=depth; ithLevel[depth]++; return; } for(int i=0;i<t[root].children.size();i++){ dfs(t[root].children[i],depth+1); } } int main(){ cin>>n>>m; fill(ithLevel,ithLevel+maxn-1,0); for(int i=0;i<m;i++){ int id,size; cin>>id>>size; for(int j=0;j<size;j++){ int child; cin>>child; t[id].children.push_back(child); } } dfs(1,0); for(int i=0;i<maxLevel;i++){ cout<<ithLevel[i]<<" "; } cout<<ithLevel[maxLevel]; return 0; }

一、题目

大意：输入节点个数n和非叶节点个数m，并在接下来的m行中以如下形式输入节点id的子节点：id 子节点个数 子节点1 子节点2……。要求输出每一层中叶节点（没有孩子的节点）的个数。

二、有问题的思路和代码

#include <iostream> using namespace std; #define MaxNum 101 typedef struct Node{ int child=0; int level=-1; }Tree[MaxNum]; int main(){ Tree tree; int n,m; cin>>n>>m; if(n==1){ cout<<"1";return 0; } tree[1].level=0; for (int i = 0; i < m; ++i) { int id,k; cin>>id>>k; for (int j = 0; j < k; ++j) { int idj; cin>>idj; tree[id].child++; tree[idj].level=tree[id].level+1;//子节点层数等于父节点层数+1 } } int Level[MaxNum]={0}; int MaxLevel=0; //记录最大深度，便于输出 for (int l = 1; l <= n; ++l) { //统计每一层叶节点的个数 if(tree[l].child==0)Level[tree[l].level]++; MaxLevel=MaxLevel>tree[l].level?MaxLevel:tree[l].level; } cout<<Level[0];//避免最后输出空格 for (int i = 1; i <= MaxLevel; ++i) { cout<<" "<<Level[i]; } return 0; }

问题在于：输入时并不一定能知道正确的父节点的层数，举个例子： 对于这棵树，如果先输入：02 1 03，再输入01 1 02。由于输入02 1 03时，02的层数还没有计算出来，而是默认值-1，这就导致03的层数是1，显然是不对的。所以总会有两个测试样例输出错误。

三、更正

等全部输入完成后，再计算层数。

#include <iostream> using namespace std; #define MaxNum 101 typedef struct Node{ int child=0;//孩子个数，这里只需要知道有没有孩子就行 int level=-1;//表示层数未知 int father; }Tree[MaxNum]; int main() { Tree tree; tree[1].level=0; tree[1].father=1;//后边计算层数的时候，会出现tree[tree[1].father]的情况 int n,m; cin>>n>>m; for (int i = 0; i < m; ++i) { int id,k; cin>>id>>k; for (int j = 0; j < k; ++j) { int idj; cin>>idj; tree[idj].father=id; tree[id].child++; } } if(n==1){//只有01一个节点时 cout<<"1"<<endl; return 0; } int i=1; while(i!=0){//区别于上一个程序的地方 i=0; for (int j = 1; j <= n; ++j) { //tree[tree[j].father].level=-1说明此时j的父节点的层数还没有计算出来，这时候没法算j的层数 if((tree[tree[j].father].level!=-1)&&(tree[j].level==-1))tree[j].level=tree[tree[j].father].level+1; //只要某个节点的父节点的层数没算出来，计算就没有完成； // 反之，如果每个节点的父节点层数一直，那么所有节点的层数就会在这一次循环中得到。 else if(tree[tree[j].father].level==-1) i++; } } int Level[MaxNum]={0}; int MaxLevel=0; //记录最大深度，便于输出 for (int l = 1; l <= n; ++l) { //统计每一层叶节点的个数 if(tree[l].child==0)Level[tree[l].level]++; MaxLevel=MaxLevel>tree[l].level?MaxLevel:tree[l].level; } cout<<Level[0];//避免最后输出空格 for (i = 1; i <= MaxLevel; ++i) { cout<<" "<<Level[i]; } return 0; }

四、总结

①、尽可能多的考虑输入情况，不要想当然。 ②、要是PTA平台能显示测试样例就好了，反正只是练习。