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

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

P15801 [GESP202603 六级] 完全二叉树

题目要求

题目描述

给定一棵包含 $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

4

输入输出样例 #2

输入 #2

4
2 3
0 0
4 0
0 0

输出 #2

3

说明/提示

对于 $40\%$ 的测试点，保证 $1\leq n\leq 500$。

对于所有测试点，保证 $1\leq n\leq 10^5$。

---

题目分析

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

完全二叉树的定义

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

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

解题思路

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

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

判断完全二叉树时，对于结点 $u$，设其左子树高度为 $h_l$、右子树高度为 $h_r$，左子树对应标记为 $l_{cbt}$、右子树对应标记为 $r_{cbt}$，可以归纳为以下合法情况：

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

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

核心逻辑图解实例

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

实例 A：左右等高（$h_l = h_r = 2$）

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

      u
    /   \
   L     R
  / \   /
 x   y z

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

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

      u
    /   \
   L     R
  /     / \
 x     y   z

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

实例 B：左比右深1层（$h_l = 3, h_r = 2$）

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

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

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

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

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

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

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

---

示例代码

标准解法（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 后序遍历
void dfs(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++;
    }
}

int main() {
    // 优化输入输出速度
    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^h - 1$”这一性质来快速判断某棵子树是否为满的，这是判定关键之一。
2. 递归深度：题目 $n \le 10^5$，极端情况下（如链状树）递归深度可达 $10^5$，部分编译环境可能导致栈溢出。实际考试中如遇到此问题，可以手动设置栈大小或改用非递归写法。

所有代码已上传至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)，考试认证学员交流，互帮互助

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