202606-满二叉树(luogu-P17013)

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

4
2 3
4 0
0 0
0 0

输出 #1

2

输入输出样例 #2

输入 #2

3
2 3
0 0
0 0

输出 #2

3

说明/提示

样例 $1$ 的树结构如下：

     (1)
     / \
   (2) (3)
   /
 (4)

其中，结点 $3$ 和结点 $4$ 各自是一个叶子结点，构成满二叉树（单个结点也是满二叉树）。结点 $2$ 只有左儿子没有右儿子，不是满二叉树。结点 $1$ 的左右子树高度不同，也不是满二叉树。因此共有 $2$ 棵满二叉树。

样例 $2$ 的树结构如下：

   (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$ 表示「不是满二叉树」。

判断逻辑如下：

1. 叶子结点（$l_u = 0$ 且 $r_u = 0$）：是满二叉树，高度为 $1$，答案计数 $+1$
2. 只有一个儿子（$l_u = 0$ 或 $r_u = 0$，但不同时为 $0$）：不是满二叉树，返回 $-1$
3. 有两个儿子：递归求左子树高度 $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$）：

满二叉树数量 $= 2$（结点 $3$ 和 $4$），与样例输出一致。

以样例 $2$ 为例（$n = 3$）：

满二叉树数量 $= 3$，与样例输出一致。

5. 复杂度分析

• 时间复杂度：每个结点恰好被访问一次，总体 $O(n)$
• 空间复杂度：存储树结构 $O(n)$，递归调用栈最坏 $O(n)$（退化为链的情况），总体 $O(n)$

6. 注意事项

• 本题给出的结点编号从 $1$ 开始，数组需要相应适配
• 递归深度最坏为 $O(n)$（退化为一条链），$n = 10^5$ 在大多数竞赛评测环境下不会栈溢出
• 单个结点（叶子）也是满二叉树，不要遗漏计数

示例代码

通过后序 DFS 递归判断每棵子树是否为满二叉树，同时统计数量。

#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，利用递归返回值携带信息的方式来高效完成。

本文由coderli.com原创，按照CC BY-NC-SA 4.0 进行授权

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

“luogu-”系列题目可在 洛谷题库 在线评测。

“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP认证交流QQ群： 688906745

GESP/CSP 认证学习微信公众号