2026年6月GESP真题及题解（C++六级）：满二叉树
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
输入 1
4 2 3 4 0 0 0 0 0输出 1
2输入输出样例 2
输入 2
3 2 3 0 0 0 0输出 2
3说明/提示
数据范围
对于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/false），h[u]记录其高度（仅在f[u]为真时有效）。采用递归后序遍历，先处理左右儿子，再计算当前结点。最终统计所有f[u] == true的结点个数。
时间复杂度：O(n)，每个结点访问一次。
空间复杂度：O(n)用于存储树和状态数组。
代码实现
#include<bits/stdc++.h>usingnamespacestd;constintN=100005;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(){cin>>n;for(inti=1;i<=n;i++)cin>>l[i]>>r[i];dfs(1);//从根结点1开始后序遍历intans=0;//计数器for(inti=1;i<=n;i++)if(f[i])ans++;//统计所有满二叉子树个数cout<<ans;return0;}功能分析
- 输入：读入结点数
n及每个结点的左右儿子编号（0 表示不存在）。 - 递归后序遍历：
dfs(u)先递归左右子树，再根据左右子树的满二叉树状态和高度计算当前结点。 - 状态判定：
- 叶子：直接标记为满，高度 0。
- 有两个儿子且二者均为满且高度相等：标记为满，高度加 1。
- 其他情况：非满，高度置 0。
- 统计：遍历所有结点，累加
f[i]为真的个数并输出。
各种学习资料，助力大家一站式学习和提升！！！
#include<bits/stdc++.h>usingnamespacestd;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++标准模板库STL：
https://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 点击跳转
· 文末祝福 ·
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}