GESP C++
6级
真题
202603-完全二叉树(luogu-P15801)

202603-完全二叉树(luogu-P15801)

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

P15801 [GESP202603 六级] 完全二叉树

题目要求

题目描述

给定一棵包含 nn 个结点的有根二叉树，结点依次以 1,2,…,n1,2,\dots,n 编号，根结点编号为 11。

对于结点 ii，其左儿子的编号记为 lil_i，右儿子编号记为 rir_i。特别地，如果左儿子不存在则 li=0l_i=0，如果右儿子不存在则 ri=0r_i=0。

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

输入格式

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

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

输出格式

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

输入输出样例 #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%40\% 的测试点，保证 1≤n≤5001\leq n\leq 500。

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

题目分析

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

完全二叉树的定义

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

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

解题思路

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

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

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

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

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

核心逻辑图解实例

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

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

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

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

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

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

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

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

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

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

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

通过后序遍历，先递归处理左右子树，再根据上述规则判断当前结点。最终统计所有 isCBT 为真的结点数量即可。整体时间复杂度为 O(n)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 满二叉树：满二叉树是完全二叉树的特殊情况——最后一层也是满的。在判定过程中，我们利用"满二叉树结点数等于 2h−12^h - 1“这一性质来快速判断某棵子树是否为满的，这是判定关键之一。
  2. 递归深度：题目 n≤105n \le 10^5，极端情况下（如链状树）递归深度可达 10510^5，部分编译环境可能导致栈溢出。实际考试中如遇到此问题，可以手动设置栈大小或改用非递归写法。

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

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

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

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

GESP/CSP认证交流QQ群： 688906745

GESP/CSP 认证学习微信公众号
GESP/CSP 认证学习微信公众号
最后更新于
202603-选数(luogu-P15800)