2026年3月GESP真题及题解C六级完全二叉树题目描述给定一棵包含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的左儿子编号和右儿子编号。输出格式输出一行一个整数表示所有子树中完全二叉树的数量。输入输出样例 1输入 14 2 3 4 0 0 0 0 0输出 14输入输出样例 2输入 24 2 3 0 0 4 0 0 0输出 23说明/提示对于40 % 40\%40%的测试点保证1 ≤ n ≤ 500 1\leq n\leq 5001≤n≤500。对于所有测试点保证1 ≤ n ≤ 10 5 1\leq n\leq 10^51≤n≤105。思路分析题目要求统计一棵有根二叉树的所有子树中有多少棵是完全二叉树。完全二叉树的定义除了最底层可能不满其余层结点数都达到最大值且最底层的结点都集中在左边。我们可以通过一次后序遍历对每个结点收集其子树的信息然后根据这些信息判断该子树是否为完全二叉树。定义空结点编号 0的高度为 0且既是满二叉树也是完全二叉树。对于每个结点需要知道h子树的高度从该结点到最深叶子的结点数根高度为 1full是否为满二叉树comp是否为完全二叉树合并规则设左儿子为 L右儿子为 R高度h max(h[L], h[R]) 1满二叉树若 L 和 R 均不存在则为满若只有一个儿子存在则不是满若两个儿子都存在则当且仅当full[L] full[R] h[L] h[R]时为满完全二叉树若 L 和 R 均不存在则是完全若 L 不存在而 R 存在则不是完全若 L 存在而 R 不存在则当且仅当comp[L] h[L] 1时为完全左子树必须是叶子若两个儿子都存在则满足以下任一条件即为完全full[L] comp[R] h[L] h[R]comp[L] full[R] h[L] h[R] 1通过自底向上计算我们可以得到每个结点的comp值统计个数即为答案。时间复杂度 O(n)空间 O(n)。为了避免递归深度过大可能达到 1e5采用迭代后序遍历。代码实现#includebits/stdc.husingnamespacestd;constintN100005;intl[N],r[N],h[N];// 左儿子、右儿子、高度boolf[N],c[N];// f: 满二叉树, c: 完全二叉树intmain(){ios::sync_with_stdio(false);cin.tie(0);intn;cinn;for(inti1;in;i){cinl[i]r[i];}// 空结点编号 0h[0]0;f[0]true;c[0]true;stackpairint,intst;// first: 结点编号, second: 阶段 (0:初始,1:左处理完,2:右处理完)st.push({1,0});while(!st.empty()){pairint,inttopst.top();intutop.first;intstatetop.second;if(state0){// 初始状态先处理左儿子state1;if(l[u])st.push({l[u],0});}elseif(state1){// 左儿子处理完处理右儿子state2;if(r[u])st.push({r[u],0});}else{// 左右儿子都已处理计算 uinthlh[l[u]],hrh[r[u]];boolflf[l[u]],frf[r[u]];boolclc[l[u]],crc[r[u]];// 高度h[u]max(hl,hr)1;// 是否为满二叉树if(!l[u]!r[u])f[u]true;elseif(!l[u]||!r[u])f[u]false;elsef[u](flfrhlhr);// 是否为完全二叉树if(!l[u]!r[u])c[u]true;elseif(!l[u])c[u]false;// 左空右非空不可能完全elseif(!r[u]){// 只有左儿子c[u]cl(hl1);// 左儿子必须是叶子}else{// 左右儿子都存在c[u](flcrhlhr)||(clfrhlhr1);}st.pop();// 当前结点计算完毕出栈}}intans0;for(inti1;in;i){if(c[i])ans;}coutans\n;return0;}功能分析数据结构l[i],r[i]存储左右儿子的编号0 表示不存在。h[i]子树高度。f[i]标记该子树是否为满二叉树。c[i]标记该子树是否为完全二叉树。下标 0 预留表示空结点并预先设好属性。迭代后序遍历使用栈模拟递归每个结点附带一个阶段变量state0刚入栈准备处理左儿子。1左儿子已处理准备处理右儿子。2左右儿子均已处理可以计算当前结点。这样可以保证在处理一个结点时它的左右子树信息已经计算完毕避免了递归栈溢出。判断逻辑高度通过左右子树最大高度加 1 得到。满二叉树的判定严格遵循定义。完全二叉树的判定依据题目要求的两种情况并正确处理只有左儿子或只有右儿子的边界情况。空结点0预先定义为满且完全使代码统一处理。复杂度每个结点恰好入栈一次、出栈一次所有操作均为 O(1)总时间复杂度 O(n)。辅助数组空间 O(n)栈深度不超过树高最坏情况下 O(n)。各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}【秘籍汇总】完整csp信奥赛C学习资料1、csp/信奥赛C完整信奥赛系列课程永久学习https://edu.csdn.net/lecturer/7901 点击跳转2、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转3、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转4、csp信奥赛冲刺一等奖有效刷题题解CSP信奥赛C初赛及复赛高频考点真题解析持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转信奥赛C提高组csp-s初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转5、GESP C考级真题题解GESP(C 一级二级三级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转GESP(C 四级五级六级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转GESP(C 七级八级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}