正确题解】GESP202603 六级 完
2026-03-20 19:17:19
发布于：浙江
2阅读
0回复
0点赞
正确题解】GESP202603 六级 完全二叉树（C++ 100 分）
一、核心定义（必须严格遵守）
- 满二叉树
所有层的节点都达到最大值，左右子树都是满二叉树，且高度相等。 - 完全二叉树（唯一正确判定规则）
一棵二叉树是完全二叉树，当且仅当满足以下两种情况之一：
左子树是满二叉树 + 右子树是完全二叉树 + 左右子树高度相等
左子树是完全二叉树 + 右子树是满二叉树 + 左子树高度 = 右子树高度 + 1
空树默认是满二叉树 + 完全二叉树。
二、解题思路
后序遍历：先算左右子树，再算当前节点（子树信息是父节点判断的基础）
记录 3 个关键信息：
子树高度
是否为满二叉树
是否为完全二叉树
统计答案：遍历所有节点，统计完全二叉树的数量
三、满分代码（C++）
cpp
运行
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 1e5 + 10;
int l[MAXN], r[MAXN]; // 左右儿子
int h[MAXN]; // 子树高度
bool full[MAXN], complete[MAXN]; // 是否满二叉树、是否完全二叉树
int ans = 0;
void dfs(int u) {
if (u == 0) {
h[u] = 0;
full[u] = true;
complete[u] = true;
return;
}
dfs(l[u]);
dfs(r[u]);
// 计算高度
h[u] = max(h[l[u]], h[r[u]]) + 1;
// 判断满二叉树
full[u] = (full[l[u]] && full[r[u]] && h[l[u]] == h[r[u]]);
// 判断完全二叉树（核心！）
int hl = h[l[u]], hr = h[r[u]];
complete[u] = false;
if (full[l[u]] && complete[r[u]] && hl == hr) {
complete[u] = true;
}
if (complete[l[u]] && full[r[u]] && hl == hr + 1) {
complete[u] = true;
}
if (complete[u]) ans++;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> l[i] >> r[i];
}
dfs(1);
cout << ans << endl;
return 0;
}
四、代码说明
数据规模：支持 n ≤ 1e5，时间复杂度 O(n)，无超时风险
快速 IO：ios::sync_with_stdio(false); cin.tie(0); 加速输入
递归安全：二叉树递归深度最大为 log n，不会栈溢出
五、样例验证
样例 1
输入：
plaintext
4
2 3
4 0
0 0
0 0
输出：4
所有子树都是完全二叉树。
样例 2
输入：
plaintext
4
2 3
0 0
4 0
0 0
输出：3
根节点不满足完全二叉树条件，其余 3 个节点满足。
这里空空如也
有帮助，赞一个