摘要本文详细讲解 PAT 甲级 1004 题Counting Leaves的解题方法。题目要求从给定的族谱树中逐层统计叶子节点数量核心思路为邻接表建树 BFS 层序遍历每层记录无孩子节点的个数。文章涵盖题目分析、样例解析、完整代码及常见错误提醒并总结时间/空间复杂度均为O(n)\mathcal{O}(n)O(n)最后给出了思维拓展方向。✅ PAT 甲级题目讲解1004《Counting Leaves》 题目简介本题要求从给定的族谱树结构中逐层统计每一层中没有孩子的节点即叶子节点个数并按照层级从上到下输出。题目中树的根节点固定为编号01输入采用非叶子节点及其所有子节点编号的形式最终输出从根节点出发每一层的叶子节点数按层次顺序打印。 样例分析输入2 1 01 1 02解释有两个节点非叶子节点有一个即01它有一个孩子02根节点01属于第 1 层但它是非叶节点节点02没有孩子是第 2 层的叶子节点。输出0 1表示第 1 层没有叶子节点第 2 层有 1 个叶子节点。 解题思路整体思路本题可以建树后使用广度优先搜索BFS从根节点开始一层层向下遍历。每一层中如果某个节点没有孩子则为叶子结点在当前层计数。 变量说明变量名含义n总结点数m非叶节点数量cnt[i]节点i的孩子数量t[i][j]节点i的第j个孩子编号s[k]第k层的叶子节点数k层数总数用于最终输出✅ Step 1建树结构使用邻接表 建树思路输入中每一行表示一个非叶子节点及其所有孩子使用二维数组t[i][j]存储节点i的第j个孩子编号另设数组cnt[i]存储每个节点的孩子个数则要遍历一棵树所有孩子可以用for(inti1;icnt[p];i){// p 有 cnt[p] 个孩子intcdt[p][i];// cd: 结点 p 的第 i 个孩子编号}根节点编号固定为01可直接以整数1表示。输入时用二维数组建树scanf(%d %d,n,m);while(m--){intf,k,c;scanf(%d %d,f,k);while(k--){scanf(%d,c);t[f][cnt[f]]c;// 记录孩子节点编号}}✅ Step 2层序遍历统计每层叶子数使用队列queueint按层推进每一层开始时记录当前队列大小size代表该层节点数逐层遍历队列中现有结点每次从队首弹出节点p判断其是否为叶子cnt[p] 0若是则s[k]将p的所有孩子依次入队每层处理结束后层数k最后一次循环后队列为空但k多加了一次因此需k--纠正。voidbfs(intx){queueintq;q.push(x);k1;// 初始化第一层为 1while(!q.empty()){intdq.size();// 当前层节点个数for(inti1;id;i){intpq.front();q.pop();if(!cnt[p])s[k];// 没有孩子就是叶子节点for(inti1;icnt[p];i){intcdt[p][i];q.push(cd);}}k;// 进入下一层}k--;// 减去最后多加的一层}✅ 完整代码#includebits/stdc.husingnamespacestd;intn,m,cnt[105],t[105][105],k,s[105];voidbfs(intx){queueintq;q.push(x);k1;// 初始化第一层while(!q.empty()){intdq.size();// 当前层的结点数for(inti1;id;i){intpq.front();q.pop();if(!cnt[p])s[k];// 当前为叶子节点for(inti1;icnt[p];i){intcdt[p][i];// 当前 p 的一个孩子q.push(cd);// 孩子入队}}k;// 层数加 1}k--;// 减去最后空的那层}intmain(){scanf(%d %d,n,m);while(m--){intf,k,c;scanf(%d %d,f,k);while(k--){scanf(%d,c);t[f][cnt[f]]c;// 建边}}bfs(1);// 从根节点 1 开始 BFSfor(inti1;ik;i){printf(%d,s[i]);if(ik)printf( );}return0;} 常见错误提醒错误类型表现描述忘记减去最后空层BFS 最后一层已空但仍加了k导致多输出一层queue 大小变化误用q.size()在for内部使用q.size()会因push()改变队列大小造成统计错误没有判断叶子节点忘记if(!cnt[p])会导致漏计✅ 总结归纳本题重点是树的建模 层序遍历熟练掌握使用数组模拟邻接表的方法每轮处理固定数量节点再推进一层注意边界处理和输出格式控制。时间复杂度建树O(n)\mathcal{O}(n)O(n)BFS 遍历O(n)\mathcal{O}(n)O(n)空间复杂度O(n)\mathcal{O}(n)O(n) 思维拓展若题目改为输出每层所有结点编号可在 BFS 中使用depth[]记录每个结点层数类似模型常见于 公司管理结构、操作系统树状调度、层级打印可视化 等问题进一步练习可尝试输出树的最大深度、树的直径、从叶子反向建树等变形题。
