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。

思路分析

判断一棵二叉树是否为满二叉树，需要满足两个条件：

1. 每个结点要么是叶子（左右儿子均为空），要么同时拥有左右两个儿子；
2. 所有叶子深度相同，即从根到任一叶子的路径长度相等。

对于任意结点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;}