【GESP】C++六级真题 luogu-P15801, [GESP202603 六级] 完全二叉树

2026年3月，GESP六级真题，考察二叉树（完全二叉树的判定），难度⭐⭐⭐☆☆。洛谷难度等级：普及/提高−。

P15801 [GESP202603 六级] 完全二叉树

题目要求

题目描述

给定一棵包含  个结点的有根二叉树，结点依次以  编号，根结点编号为 。

对于结点 ，其左儿子的编号记为 ，右儿子编号记为 。特别地，如果左儿子不存在则 ，如果右儿子不存在则 。

树中每个结点都对应一棵以其为根的子树。请你求出给定有根树的所有  棵子树中，有多少棵子树是完全二叉树。

输入格式

第一行，一个正整数 ，表示有根二叉树结点数量。

接下来  行，每行两个正整数 ，表示结点  的左儿子编号和右儿子编号。

输出格式

输出一行，一个整数，表示所有子树中完全二叉树的数量。

输入输出样例 #1

输入 #1

42 34 00 00 0

输出 #1

4

输入输出样例 #2

输入 #2

42 30 04 00 0

输出 #2

3

说明/提示

对于  的测试点，保证 。

对于所有测试点，保证 。

题目分析

本题需要判定一棵有根二叉树中的每棵子树是否为完全二叉树，并统计数量。

完全二叉树的定义

一棵深度为  的二叉树是完全二叉树，需要满足：

• 除最后一层外，每一层的结点数都达到最大值（即满的）；
• 最后一层的结点全部靠左排列。

解题思路

我们可以通过一次 DFS（后序遍历），自底向上地为每个结点  计算三个信息：

1. height[u] ：以  为根的子树的高度（叶结点高度为 ）。
2. size[u] ：以  为根的子树的结点数。
3. isCBT[u] ：以  为根的子树是否是完全二叉树。

判断完全二叉树时，对于结点 ，设其左子树高度为 、右子树高度为 ，左子树对应标记为 、右子树对应标记为 ，可以归纳为以下合法情况：

1.  是叶结点（无左右儿子）：显然是完全二叉树。
2.  只有左儿子（左儿子是叶结点，右儿子不存在）：即只有一个左叶子，这是完全二叉树最后一层只有一个靠左结点的特殊情况。
3.  有左右儿子，且左右等高（）：说明此时左边子树的“坑位”已经被彻底填满了，才轮到右边子树开始填同层结点。因此必须满足：
• 左子树必须是满二叉树。在代码中只要看左子树的结点数是否刚好等于  即可。
• 右子树必须是一棵合法的完全二叉树（不管它底层有没有填满）。
4.  有左右儿子，且左边比右边刚好深 1 层（）：左边比右边深，说明现在正在填左侧最下面的一层，还没轮到右侧。因此必须满足：
• 右子树必须是满二叉树。由于右边还没开始长这一层，它原有的高度  必须是满的，不缺角。
• 左子树必须是一棵合法的完全二叉树（正在填底层，没有违规空缺）。

如果出现右边比左边高、或者左边比右边高出 2 层及以上等其他情况，则直接判定为假（违反了从左到右、层层递进的原则）。

核心逻辑图解实例

为了更好理解情况 3 和情况 4 的判定逻辑，我们来看几个具体的“盖楼”例子（我们在判断整体树根  是否为完全二叉树）：

实例 A：左右等高（）

【合法情况（左边填满了）】

      u    /   \   L     R  / \   / x   y z

• 分析：左子树  的“坑位”是全满的（这是一棵满二叉树，结点数为 ）。右子树  正在长最后一层。此时底盘是结结实实挨着左边填的， 是一棵完全二叉树。

【非法情况（左边都没填满）】

      u    /   \   L     R  /     / \ x     y   z

• 分析：左子树  缺了右脚（结点数为 ，它不是满的）。既然左边那个楼的坑位都没填满，右子树  根本没资格开始继续往下长新楼层！直接判定 不是完全二叉树。

实例 B：左比右深1层（）

【合法情况（右边地基是满的）】

        u      /   \     L     R    / \   / \   x   y z   w  / a

• 分析：左子树  刚探出去长了第 3 层（结点 ）。要想合法，右树  之前停留在第 2 层的状态必须是全满无死角的（要求它是满二叉树，结点数为 ），否则这说明没填满就越级了。此时  是完全二叉树。

【非法情况（右边地基不满）】

        u      /   \     L     R    / \   /   x   y z       <-- w 缺席，右边层没满  / a

• 分析：右子树  的第 2 层根本没满（缺了  结点）。既然右边都没填平这一层，左侧凭什么偷偷向下长出第 3 层的结点 ？这严重违反了整棵树“层层填平”的原则，直接判定 不是完全二叉树。

通过后序遍历，先递归处理左右子树，再根据上述规则判断当前结点。最终统计所有 isCBT 为真的结点数量即可。整体时间复杂度为 。

示例代码

标准解法（DFS 后序遍历判定）

#include<iostream>#include<vector>const int MAXN = 100005;int l_child[MAXN], r_child[MAXN]; // 左右儿子int height_val[MAXN]; // 子树高度int sz[MAXN]; // 子树结点数bool isCBT[MAXN]; // 是否为完全二叉树int ans = 0; // 完全二叉树计数// DFS 后序遍历voiddfs(int u){    // 空结点，直接返回    if (u == 0) {        return;    }    // 递归处理左右子树    dfs(l_child[u]);    dfs(r_child[u]);    int L = l_child[u];    int R = r_child[u];    // 计算高度和结点数    height_val[u] = std::max(height_val[L], height_val[R]) + 1;    sz[u] = sz[L] + sz[R] + 1;    // 判断是否为完全二叉树    isCBT[u] = false;    if (L == 0 && R == 0) {        // 情况1：叶结点，一定是完全二叉树        isCBT[u] = true;    } else if (L != 0 && R == 0) {        // 情况2：只有左儿子，左儿子必须是叶结点        if (height_val[L] == 1) {            isCBT[u] = true;        }    } else if (L != 0 && R != 0) {        // 情况3：左右儿子都存在        int hl = height_val[L], hr = height_val[R];        if (hl == hr) {            // 左右等高：左子树必须是满二叉树，右子树是完全二叉树            // 满二叉树结点数 = 2^h - 1            if (sz[L] == (1 << hl) - 1 && isCBT[L] && isCBT[R]) {                isCBT[u] = true;            }        } else if (hl == hr + 1) {            // 左比右高1：右子树必须是满二叉树，左子树是完全二叉树            if (sz[R] == (1 << hr) - 1 && isCBT[L] && isCBT[R]) {                isCBT[u] = true;            }        }        // 其他高度差情况，不是完全二叉树    }    // 只有右儿子没有左儿子的情况，不是完全二叉树    if (isCBT[u]) {        ans++;    }}intmain(){    // 优化输入输出速度    std::ios_base::sync_with_stdio(false);    std::cin.tie(NULL);    int n;    std::cin >> n;    // 初始化空结点的高度和结点数为 0    height_val[0] = 0;    sz[0] = 0;    for (int i = 1; i <= n; i++) {        std::cin >> l_child[i] >> r_child[i];    }    // 从根结点（编号1）开始 DFS    dfs(1);    std::cout << ans << "\n";    return 0;}

代码解析小贴士

1. 完全二叉树 vs 满二叉树：满二叉树是完全二叉树的特殊情况——最后一层也是满的。在判定过程中，我们利用"满二叉树结点数等于 "这一性质来快速判断某棵子树是否为满的，这是判定关键之一。
2. 递归深度：题目 ，极端情况下（如链状树）递归深度可达 ，部分编译环境可能导致栈溢出。实际考试中如遇到此问题，可以手动设置栈大小或改用非递归写法。

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

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