2026年6月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_i 0li​0如果右儿子不存在则r i 0 r_i 0ri​0。树中每个结点都对应一棵以其为根的子树。请你求出给定有根树的所有n nn棵子树中有多少棵子树是满二叉树。满二叉树是指所有叶子深度均相同且除叶子外均有两个儿子的二叉树例如以下三棵二叉树均是满二叉树() () () / \ / \ () () () () / \ / \ () ()() ()在上面这棵有3 33个节点的二叉树中有3 33个子树是满二叉树包括整个树本身及所有的单个叶子节点又例如(1) / \ (2) (3) / \ (4) (5)在上面这棵有5 55个节点的二叉树中有4 44个子树是满二叉树包括节点3 33的子树以及所有单个叶子节点。输入格式第一行一个正整数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输出 12输入输出样例 2输入 23 2 3 0 0 0 0输出 23说明/提示数据范围对于40 % 40\%40%的测试点保证1 ≤ n ≤ 500 1 \le n \le 5001≤n≤500。对于所有测试点保证1 ≤ n ≤ 10 5 1 \le n \le 10^51≤n≤105。思路分析判断一棵二叉树是否为满二叉树需要满足两个条件每个结点要么是叶子左右儿子均为空要么同时拥有左右两个儿子所有叶子深度相同即从根到任一叶子的路径长度相等。对于任意结点u我们可以递归地判断其子树若u是叶子则其子树是满二叉树高度为0若u同时存在左儿子L和右儿子R则只有当L和R的子树都是满二叉树且高度相等时u的子树才是满二叉树高度为h[L] 1否则只有一个儿子或左右子树高度不等或非满u的子树不是满二叉树。用数组f[u]记录结点u的子树是否为满二叉树true/falseh[u]记录其高度仅在f[u]为真时有效。采用递归后序遍历先处理左右儿子再计算当前结点。最终统计所有f[u] true的结点个数。时间复杂度O(n)每个结点访问一次。空间复杂度O(n)用于存储树和状态数组。代码实现#includebits/stdc.husingnamespacestd;constintN100005;intn,l[N],r[N];// l[i]:i的左儿子, r[i]:i的右儿子boolf[N];//标记以i为根的子树是否为满二叉树inth[N];//记录以i为根的满二叉树的高度//深度优先后序遍历计算每个结点的满二叉树状态和高度voiddfs(intu){if(!u)return;//空结点直接返回dfs(l[u]);//递归处理左子树dfs(r[u]);//递归处理右子树if(!l[u]!r[u]){//当前结点是叶子(无左右儿子)f[u]1;//标记为满二叉树h[u]0;//高度为0}elseif(l[u]r[u]f[l[u]]f[r[u]]h[l[u]]h[r[u]]){//有两个儿子且左右子树均为满二叉树且高度相等f[u]1;//当前子树也是满二叉树h[u]h[l[u]]1;//高度为左子树高度1}else{//不满足满二叉树条件f[u]0;//标记为非满h[u]0;//高度置0}}intmain(){cinn;for(inti1;in;i)cinl[i]r[i];dfs(1);//从根结点1开始后序遍历intans0;//计数器for(inti1;in;i)if(f[i])ans;//统计所有满二叉子树个数coutans;return0;}功能分析输入读入结点数n及每个结点的左右儿子编号0 表示不存在。递归后序遍历dfs(u)先递归左右子树再根据左右子树的满二叉树状态和高度计算当前结点。状态判定叶子直接标记为满高度 0。有两个儿子且二者均为满且高度相等标记为满高度加 1。其他情况非满高度置 0。统计遍历所有结点累加f[i]为真的个数并输出。各种学习资料助力大家一站式学习和提升#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 点击跳转https://edu.csdn.net/course/detail/41081 点击跳转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信奥赛冲刺一等奖有效刷题题解信奥赛C普及组CSP-J一等奖通关刷题题单及题解https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转信奥赛C普及组csp-j初赛复赛真题题解持续更新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;}