文章目錄

• • 題目分析
  • 題目鏈接

題目分析

題意重述：一棵樹(shù)，求每一層的葉子節(jié)點(diǎn)數(shù)目。

分析 構(gòu)造樹(shù)，使用鄰接表來(lái)存（相當(dāng)于存儲(chǔ)有向圖）。

需要一個(gè)頭結(jié)點(diǎn)數(shù)組h[N]，然后每個(gè)頭節(jié)點(diǎn)往外形成一個(gè)單鏈表e[],ne[];(用數(shù)組模擬)單鏈表中用來(lái)存該結(jié)點(diǎn)的孩子結(jié)點(diǎn)，用cnt[N]數(shù)組來(lái)記錄每一層的葉子結(jié)點(diǎn)數(shù)。

使用深度優(yōu)先遍歷dfs來(lái)求每一層的葉子節(jié)點(diǎn)數(shù)，由于是鄰接表式的存儲(chǔ)，頭結(jié)點(diǎn)數(shù)組中某結(jié)點(diǎn)值是-1，表示是葉子結(jié)點(diǎn)，這也就是dfs的退出的條件，此時(shí)如何退出呢？ 需要將該葉子結(jié)點(diǎn)所在層數(shù)的葉子數(shù)++，然后記得更新樹(shù)的最大深度。

然后深度遍歷該結(jié)點(diǎn)的孩子結(jié)點(diǎn)。

ac代碼

#include<bits/stdc++.h> using namespace std;const int N=110; int n,m; //用鄰接表來(lái)存 int h[N], e[N],ne[N], idx; //idx默認(rèn)初始化為0int cnt[N] ;// 每一層的葉子結(jié)點(diǎn)數(shù)int max_depth; //樹(shù)的最大層數(shù)void add(int a, int b){ //使用頭結(jié)點(diǎn)a的鏈表 h[a]//在a這個(gè)單鏈表內(nèi)，插入結(jié)點(diǎn)b(頭插法)//表示a有一個(gè)兒子b//e[ ] 存的是結(jié)點(diǎn)號(hào)b//ne [ ] 中存的是下一個(gè)結(jié)點(diǎn)序號(hào)idx，不是結(jié)點(diǎn)號(hào)e[idx] =b,ne[idx] =h[a],h[a]=idx++;//cout<< a<<' '<<b<<endl; }void dfs(int u, int depth){if(h[u]==-1){ //說(shuō)明u是葉子結(jié)點(diǎn)cnt[depth]++;//depth這一層的計(jì)數(shù)++max_depth=max(max_depth,depth);return;}//遍歷頭結(jié)點(diǎn)u對(duì)應(yīng)的單鏈表h[u]for(int i =h[u]; i!=-1; i=ne[i]){dfs(e[i],depth+1);//}}int main(){cin>> n>> m;memset(h ,-1,sizeof h);for(int i=0;i<m;i++){int id ,k;cin>> id >> k;while(k--){int son;cin>>son;add(id , son);//構(gòu)造鄰接表}}dfs(1,0); //結(jié)點(diǎn)號(hào)，層數(shù)cout<<cnt[0];for(int i=1;i<=max_depth;i++) cout<<" "<<cnt[i];}

題目鏈接

PAT甲級(jí)1004 Counting Leaves (30分)

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的PAT甲级1004 Counting Leaves (30分)：[C++题解]树、邻接表存储树、dfs遍历树的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。