本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P15801 [GESP202603 六级] 完全二叉树 - 洛谷【题目描述】给定一棵包含n nn个结点的有根二叉树结点依次以1 , 2 , … , n 1,2,\dots,n1,2,…,n编号根结点编号为1 11。对于结点i ii其左儿子的编号记为l i l_ili​右儿子编号记为r i r_iri​。特别地如果左儿子不存在则l i 0 l_i0li​0如果右儿子不存在则r i 0 r_i0ri​0。树中每个结点都对应一棵以其为根的子树。请你求出给定有根树的所有n nn棵子树中有多少棵子树是完全二叉树。【输入】第一行一个正整数n nn表示有根二叉树结点数量。接下来n nn行每行两个正整数l i , r i l_i,r_ili​,ri​表示结点i ii的左儿子编号和右儿子编号。【输出】输出一行一个整数表示所有子树中完全二叉树的数量。【输入样例】4 2 3 4 0 0 0 0 0【输出样例】4【解题思路】【算法标签】#普及# #DFS-树#【代码详解】#includebits/stdc.husingnamespacestd;constintN100005;intn,ans;structtree{intl,r,cnt,dep,flag;}tr[N];voiddfs(intu){intlchildtr[u].l,rchildtr[u].r;// 如果是叶子节点if(lchild0rchild0){tr[u].cnt1;// 节点计数为1tr[u].dep1;// 深度为1tr[u].flag1;// 标记为完全二叉树ans;// 计数加1return;}tr[u].cnt1;// 初始化计数包含当前节点自身// 遍历左子树if(tr[u].l){dfs(tr[u].l);tr[u].cnttr[lchild].cnt;// 累加左子树的节点数tr[u].deptr[lchild].dep1;// 计算深度}// 遍历右子树if(tr[u].r){dfs(tr[u].r);tr[u].cnttr[rchild].cnt;// 累加右子树的节点数tr[u].depmax(tr[u].dep,tr[rchild].dep1);// 更新最大深度}// 处理只有一个子节点的情况if(tr[lchild].dep1tr[rchild].dep0){tr[rchild].flag1;}// 如果左右子树都是完全二叉树if(tr[lchild].flag1tr[rchild].flag1){// 情况1: 左右子树深度相等if(tr[lchild].deptr[rchild].deptr[lchild].cnt(1tr[lchild].dep)-1){tr[u].flag1;// 当前节点是完全二叉树的根ans;}// 情况2: 左子树深度比右子树大1elseif(tr[lchild].deptr[rchild].dep1tr[rchild].cnt(1tr[rchild].dep)-1){tr[u].flag1;// 当前节点是完全二叉树的根ans;}}}intmain(){cinn;for(inti1;in;i){intl,r;cinlr;tr[i].ll,tr[i].rr;}dfs(1);coutansendl;return0;}【运行结果】4 2 3 4 0 0 0 0 0 4