【GESP】C++六级真题 luogu-P17013, [GESP202606 六级] 满二叉树
GESP C++六级2026年6月真题。本题考查二叉树的递归遍历（DFS），要求判断以每个结点为根的子树是否为满二叉树，并统计满二叉树的数量。难度⭐⭐。本题在洛谷评定为普及-。
P17013 [GESP202606 六级] 满二叉树
题目要求
题目描述
给定一棵包含 $n$ 个结点的有根二叉树，结点依次以 $1, 2, \dots, n$ 编号，根结点编号为 $1$。
对于结点 $i$，其左儿子的编号记为 $l_i$，右儿子编号为 $r_i$。特别地，如果左儿子不存在则 $l_i = 0$，如果右儿子不存在则 $r_i = 0$。
树中每个结点都对应一棵以其为根的子树。请你求出给定有根树的所有 $n$ 棵子树中，有多少棵子树是满二叉树。
满二叉树是指所有叶子深度均相同，且除叶子外均有两个儿子的二叉树。
输入格式
第一行，一个正整数 $n$，表示有根二叉树结点数量。
接下来 $n$ 行，每行两个非负整数 $l_i, r_i$，表示结点 $i$ 的左儿子编号和右儿子编号，整数之间以空格分隔。
输出格式
输出一行，一个整数，表示所有子树中满二叉树的数量。
输入输出样例 #1
输入 #1
1
2
3
4
5
4
2 3
4 0
0 0
0 0
输出 #1
1
2
输入输出样例 #2
输入 #2
1
2
3
4
3
2 3
0 0
0 0
输出 #2
1
3
说明/提示
样例 $1$ 的树结构如下：
1
2
3
4
5
(1)
/ \
(2) (3)
/
(4)
其中，结点 $3$ 和结点 $4$ 各自是一个叶子结点，构成满二叉树（单个结点也是满二叉树）。结点 $2$ 只有左儿子没有右儿子，不是满二叉树。结点 $1$ 的左右子树高度不同，也不是满二叉树。因此共有 $2$ 棵满二叉树。
样例 $2$ 的树结构如下：
1
2
3
(1)
/ \
(2) (3)
结点 $2$ 和 $3$ 各自是叶子（满二叉树），整棵树也是满二叉树。共 $3$ 棵。
数据范围
对于 $40\%$ 的测试点，保证 $1 \le n \le 500$。
对于所有测试点，保证 $1 \le n \le 10^5$。
题目分析
本题考查对满二叉树定义的理解和 递归（DFS） 的应用。需要遍历树中的每个结点，判断以它为根的子树是否为满二叉树。
1. 满二叉树的定义回顾
满二叉树要求：
- 每个非叶子结点都恰好有两个儿子（左右儿子都存在）
- 所有叶子结点的深度相同
由此可以推出：满二叉树的结点数为 $2^h - 1$，其中 $h$ 是树的高度（层数）。例如：
- 高度 $1$：$1$ 个结点（单个叶子）
- 高度 $2$：$3$ 个结点
- 高度 $3$：$7$ 个结点
单个结点也是满二叉树（高度为 $1$，$0$ 片叶子都在同一层，且没有非叶子结点需要检查）。
2. 递归判断思路
对于一棵以结点 $u$ 为根的子树，我们通过后序遍历（DFS）来判断它是否为满二叉树。定义一个递归函数 dfs(u)，返回以 $u$ 为根的子树的高度（若该子树是满二叉树），否则返回 $-1$ 表示「不是满二叉树」。
判断逻辑如下：
- 叶子结点（$l_u = 0$ 且 $r_u = 0$）：是满二叉树，高度为 $1$，答案计数 $+1$
- 只有一个儿子（$l_u = 0$ 或 $r_u = 0$，但不同时为 $0$）：不是满二叉树，返回 $-1$
- 有两个儿子：递归求左子树高度 $h_l$ 和右子树高度 $h_r$
- 若 $h_l \neq -1$ 且 $h_r \neq -1$ 且 $h_l = h_r$：左右子树都是满二叉树且高度相同，因此以 $u$ 为根的子树也是满二叉树，答案计数 $+1$，返回 $h_l + 1$
- 否则：不是满二叉树，返回 $-1$
3. 为什么左右子树高度相同就够了？
这一步是关键。如果左右子树各自都是满二叉树且高度相同，那么：
- 左右子树内部所有叶子的深度分别相同（满二叉树性质）
- 左右子树高度相同 $\Rightarrow$ 合并后所有叶子深度仍然相同
- 根结点 $u$ 有两个儿子
因此，以 $u$ 为根的子树满足满二叉树的所有条件。
4. 样例验证
以样例 $1$ 为例（$n = 4$）：
| 结点 | 左儿子 | 右儿子 | DFS 结果 | 是否满二叉树？ |
|---|---|---|---|---|
| $4$ | $0$ | $0$ | 叶子，高度 $= 1$ | ✓ |
| $3$ | $0$ | $0$ | 叶子，高度 $= 1$ | ✓ |
| $2$ | $4$ | $0$ | 只有左儿子，返回 $-1$ | ✗ |
| $1$ | $2$ | $3$ | 左子树返回 $-1$，返回 $-1$ | ✗ |
满二叉树数量 $= 2$（结点 $3$ 和 $4$），与样例输出一致。
以样例 $2$ 为例（$n = 3$）：
| 结点 | 左儿子 | 右儿子 | DFS 结果 | 是否满二叉树？ |
|---|---|---|---|---|
| $2$ | $0$ | $0$ | 叶子，高度 $= 1$ | ✓ |
| $3$ | $0$ | $0$ | 叶子，高度 $= 1$ | ✓ |
| $1$ | $2$ | $3$ | $h_l = 1, h_r = 1$，相等，高度 $= 2$ | ✓ |
满二叉树数量 $= 3$，与样例输出一致。
5. 复杂度分析
- 时间复杂度：每个结点恰好被访问一次，总体 $O(n)$
- 空间复杂度：存储树结构 $O(n)$，递归调用栈最坏 $O(n)$（退化为链的情况），总体 $O(n)$
6. 注意事项
- 本题给出的结点编号从 $1$ 开始，数组需要相应适配
- 递归深度最坏为 $O(n)$（退化为一条链），$n = 10^5$ 在大多数竞赛评测环境下不会栈溢出
- 单个结点（叶子）也是满二叉树，不要遗漏计数
示例代码
通过后序 DFS 递归判断每棵子树是否为满二叉树，同时统计数量。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
int l[100005]; // l[i] 表示结点 i 的左儿子编号，0 表示不存在
int r[100005]; // r[i] 表示结点 i 的右儿子编号，0 表示不存在
int ans = 0; // 满二叉树的计数
// DFS 函数：返回以 u 为根的子树的高度（若该子树是满二叉树），否则返回 -1
int dfs(int u) {
// 情况 1：叶子结点（没有左儿子也没有右儿子）
// 单个结点构成满二叉树，高度为 1
if (l[u] == 0 && r[u] == 0) {
ans++; // 计数 +1
return 1;
}
// 情况 2：只有一个儿子（不是满二叉树，因为满二叉树要求非叶子结点必须有两个儿子）
if (l[u] == 0 || r[u] == 0) {
// 虽然当前子树不是满二叉树，但仍需递归处理存在的那个子树
// 因为那个子树中可能包含满二叉树的子树
if (l[u] != 0) dfs(l[u]);
if (r[u] != 0) dfs(r[u]);
return -1;
}
// 情况 3：有两个儿子，递归判断左右子树
int hl = dfs(l[u]); // 左子树的高度（-1 表示不是满二叉树）
int hr = dfs(r[u]); // 右子树的高度（-1 表示不是满二叉树）
// 左右子树都是满二叉树且高度相同，则以 u 为根的子树也是满二叉树
if (hl != -1 && hr != -1 && hl == hr) {
ans++; // 计数 +1
return hl + 1; // 整棵子树的高度 = 子树高度 + 1（当前结点这一层）
}
// 否则，以 u 为根的子树不是满二叉树
return -1;
}
int main() {
int n;
std::cin >> n;
// 读入每个结点的左右儿子编号
for (int i = 1; i <= n; i++) {
std::cin >> l[i] >> r[i];
}
// 从根结点（编号 1）开始 DFS
dfs(1);
// 输出满二叉树的数量
std::cout << ans << std::endl;
return 0;
}
拓展思考
本题用到的「返回值表示合法性和高度信息」的递归技巧非常实用。类似的思路还可以用于判断：
- 完全二叉树：所有叶子集中在最后一层或倒数第二层，且最后一层的叶子靠左对齐
- 平衡二叉树（AVL 树）：每个结点的左右子树高度差不超过 $1$
- 二叉搜索树（BST）：每个结点的值大于左子树中所有值，小于右子树中所有值
这些判断都可以通过一次 DFS，利用递归返回值携带信息的方式来高效完成。
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
GESP 学习专题站：GESP WIKI
"luogu-"系列题目可在洛谷题库进行在线评测。
"bcqm-"系列题目可在编程启蒙题库进行在线评测。
欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答
欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总
欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助
