GESP 题解库 / 6 级题解 / [GESP202603 六级] 完全二叉树 · 第 1 / 27 题
GESP202603 六级 · P15801 · 中等

完全二叉树

给定一棵 n 个结点的有根二叉树,每个结点的左右儿子都已给出,
请统计所有 n 棵子树里,有多少棵是完全二叉树。

📊
n ≤ 10⁵
数据规模
🌳
二叉树
数据结构
⚡
O(n)
时间复杂度
🎯
后序 DP
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

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

对于结点 i,其左儿子的编号记为 lᵢ,右儿子编号记为 rᵢ。特别地,如果左儿子不存在则 lᵢ = 0,如果右儿子不存在则 rᵢ = 0。

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

💡
人话翻译:题目把每个结点的左右孩子都告诉你了。你需要盯着这棵树看: 以每个结点为"根"往下看,能组成一棵小树(子树),一共 n 个小树。 问这些小树里,有几棵长得"规规矩矩"(完全二叉树)。注意:叶子结点自己也算一棵子树。

🔍 关键词提取

有根二叉树 完全二叉树 子树计数 后序遍历 树形 DP

已知条件

项目说明
树的规模n 个结点,编号 1 ∼ n
根结点固定为编号 1
输入格式第一行 n;接下来 n 行,第 i 行是 lᵢ rᵢ
孩子约定不存在时记 0;不保证孩子编号大于父结点
输出所有子树中「完全二叉树」的棵数
数据范围40% 测试点 n ≤ 500;全部测试点 n ≤ 10⁵

需要解决的问题

⚠️
注意"计数对象":题目数的是所有 n 棵子树(每个结点各贡献一棵),不是"整棵树是不是完全二叉树"这一个是非判断。 所以答案最小也有叶子结点那么多。
02
思维导图
整理解题思路的全貌
🌳 统计完全二叉树子树
📥 输入建模
1️⃣根固定为 1 号结点
📦数组 lc[]、rc[] 存左右孩子
0️⃣0 表示孩子不存在
🚫不保证孩子编号更大
📏 判定三要素
📐高度 h:最长链的长度
🟩满 full:结点数 = 2ʰ−1
✅完全 cmpl:本题要求的性质
🔗满 ⇒ 完全,反之不成立
🔁 递推设计
⬇️后序遍历:先算左右孩子
📤每个结点返回三元组
⚖️比较左右高度 hl、hr
⏱️每个结点 O(1) 合并
🕳️ 边界与陷阱
🌱空子树:h=0、满=真、完全=真
➡️只有右孩子 ⇒ 必定不完全
🪜链状树深度可达 10⁵
💥递归可能爆栈,需迭代
03
样例手算推导
两个样例只差一个孩子,答案却不一样

🌲 先看清两棵树长什么样

两个样例都是 n=4,输入只差一行,但答案分别是 4 和 3。区别就在结点 2 和结点 3 谁有孩子。

样例 1:4 棵子树全为完全二叉树 → 答案 4 1 2 3 4 h=3 h=2 h=1 h=1 左子树高 2、右子树高 1 → 矮的一边在右边 ✓ 样例 2:只有 3 棵完全二叉树 → 答案 3 1 2 3 4 h=3 h=1 h=2 h=1 左子树高 1、右子树高 2 → 矮的一边在左边 ✗
绿色 = 该结点为根的子树是完全二叉树;红色 = 不是
🔑
一眼看出区别:完全二叉树要求结点"从上到下、从左到右"紧密排列,所以左右子树的高度差最多是 1,而且只允许"左边更高"。 样例 1 里结点 1 的左子树更高(矮的靠右)→ 可以;样例 2 里右子树更高(矮的靠左)→ 不行。

🧮 样例 2 逐结点推演

我们用"后序"的顺序(先孩子、后自己)逐个结点算,每一步都记录三个量:高度 h、是否满 full、是否完全 cmpl。

1
结点 2(叶子)

左右孩子都是 0。按约定空子树 h=0、满=真、完全=真。

于是 h₂ = (0,0)+1 = 1;hl=hr=0 → 满 = 真,完全 = 左满 ∧ 右完全 = 真

✅ 完全 → 计数 1

2
结点 4(叶子)

同样是叶子:h₄ = 1,满 = 真,完全 = 真。

✅ 完全 → 计数 2

3
结点 3(左孩子 4,右孩子空)

取 h₄ = 1、右孩子为空 h=0 → hl = 1, hr = 0

满足 hl = hr + 1 → 完全 = 完全左 ∧ 满右 = 真 ∧ 真(空子树) = 真

h₃ = (1,0)+1 = 2;因为 hl ≠ hr,所以满 = 假

✅ 完全 → 计数 3

4
结点 1(左孩子 2,右孩子 3)

取 h₂ = 1, h₃ = 2 → hl = 1, hr = 2

先比 hl = hr?1 ≠ 2,不成立

再比 hl = hr + 1?1 ≠ 3,也不成立

→ 完全 = 假,即使结点 2、3 两棵子树都完全也没用

❌ 不完全

📊 汇总统计

结点左 · 右hl · hr高度 h满?完全?累计
2— · —0 · 01是✅ 是1
4— · —0 · 01是✅ 是2
34 · —1 · 02否✅ 是3
12 · 31 · 23否❌ 否3

最终答案:3 棵 ✓

❓ 为什么「只有左孩子」可以,「只有右孩子」不行?

这是本题最容易记混的一点,用"层序排列"的视角看就很清楚:

情形层序展开图是否完全原因
只有左孩子 父 → 左(左边填满,右边空着) ✅ 是 最后一层的结点仍然"靠左排"
只有右孩子 父 → 空 → 右(中间挖了个洞) ❌ 否 右边的位置被占了,左边却空着,不满足"靠左"
⚠️
对应到公式:只有右孩子时 hl = 0、hr ≥ 1, 既不可能满足 hl = hr,也不可能满足 hl = hr + 1, 所以自动落入"其他情况 → 完全 = 假"。公式天然处理了这个坑,不用特判。
04
解法对比
暴力能过 40%,正解才能满分

⚔️ 两种解法大比拼

🟠 解法一:逐棵独立判定

对每个结点,用它自己为根做一次 BFS,检查是否出现"空孩子之后又出现非空孩子"

  • 单次判定:O(子树大小)
  • 总复杂度:O(n²)(链状树时 ∑size = n²/2)
  • n = 500:约 12 万次 → 轻松通过 40%
  • n = 10⁵:约 5×10⁹ 次 → TLE
⚠️
同一棵子树会被反复扫描——父结点判定时又要把孩子全走一遍,做了大量重复功。

🟢 解法二:后序 DP 推荐

每个结点只算一次,把 (高度, 是否满, 是否完全) 直接交给父结点用

  • 每个结点合并代价:O(1)
  • 总复杂度:O(n)
  • n = 10⁵:约 10⁵ 次 → 稳过满分
  • 额外空间:仅 3 个数组
💡
核心思想:子树的结论可以被父结点复用, 这就是"树形 DP"——把递归的返回值当作状态。

📈 性能对比

n 的规模逐棵判定(O(n²))后序 DP(O(n))现实结果
500(40% 测试点)约 12 万次约 500 次两者都能过
10,000约 5×10⁷ 次约 10⁴ 次尚可,已偏慢
100,000(满分要求)约 5×10⁹ 次约 10⁵ 次暴力超时,DP 稳过
🎯
比赛策略:先写 O(n²) 的暴力拿下 40% 的分,再改成后序 DP 拿满分。 本题 DP 的代码量并不比暴力多多少,时间充裕的话直接上 DP 更稳。
05
算法流程图
一次后序遍历,三个量定乾坤

📐 后序 DP 执行流程

还有结点未访问 → 回到后序遍历 hl == hr hl == hr + 1 其他情况 是 ✓ 否 ✗ 开始 读入 n、lc[]、rc[] 后序遍历访问结点 u 先递归左右孩子,取 hl、hr 与左右标记 hl 与 hr 的关系? 决定满与完全 满 = 满L 且 满R 完全 = 满L 且 完全R 满 = 假 完全 = 完全L 且 满R 满 = 假 完全 = 假 h = max(hl, hr) + 1 完全 = 真? ans++ 不计数 回溯;所有结点都访问完了? 输出 ans 结束
← 左右滑动查看完整流程图

🔑 空子树约定:让叶子"免费"通过

如果我们规定空子树的高度为 0、是满二叉树、也是完全二叉树,那么叶子结点就不用单独写分支了:

结点类型hl · hr套用公式结果
叶子(左右皆空) 0 · 0 hl == hr → 满 = 满L ∧ 满R;完全 = 满L ∧ 完全R 满 = 真,完全 = 真,h = 1 ✓
✨
这正是好写法的体现:不需要写 if (是叶子) 的特判。 统一约定边界值,代码的分支数就少一层,出错概率也低——这是树形 DP 里非常常用的技巧。
06
动手算一算
输入一棵树,看它每棵子树是否完全

🌳 完全二叉树子树计算器

第一行输入结点数 n,接下来 n 行每行两个数表示左、右孩子编号(不存在填 0)。

分析结果会显示在这里

点"算一下"按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码(递归后序)

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
int n;
int lc[MAXN], rc[MAXN];   // 左右孩子,0 表示空
int h[MAXN];               // 子树高度
bool full[MAXN];            // 是否满二叉树
bool cmpl[MAXN];            // 是否完全二叉树
int ans = 0;

void dfs(int u) {
    if (u == 0) return;          // 空子树直接返回

    dfs(lc[u]);                     // ① 后序:先算左孩子
    dfs(rc[u]);                     // ② 再算右孩子

    // ③ 取左右子树信息;空子树的 h = 0
    int hl = h[lc[u]], hr = h[rc[u]];
    // 空子树视为"满"和"完全"
    bool fl = (lc[u] == 0) || full[lc[u]];
    bool fr = (rc[u] == 0) || full[rc[u]];
    bool cl = (lc[u] == 0) || cmpl[lc[u]];
    bool cr = (rc[u] == 0) || cmpl[rc[u]];

    // ④ 高度:左右取较大者再加 1(叶子得到 1)
    h[u] = max(hl, hr) + 1;

    // ⑤ 满:两侧等高,且两侧都满
    full[u] = (hl == hr) && fl && fr;

    // ⑥ 完全:三种情况
    if (hl == hr)            cmpl[u] = fl && cr;  // 等高 → 左满、右完全
    else if (hl == hr + 1)    cmpl[u] = cl && fr;  // 左高一 → 左完全、右满
    else                     cmpl[u] = false;    // 其他 → 一定不完全

    if (cmpl[u]) ans++;              // ⑦ 是就计数
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &lc[i], &rc[i]);
    dfs(1);                        // 从根出发
    printf("%d\n", ans);
    return 0;
}

📖 关键几行怎么看

代码作用为什么这样写
if (u == 0) return; 遇到空结点直接返回 数组下标 0 对应的 h[0] 天然是 0,模拟"空子树高度为 0"
fl = (lc[u]==0) || full[lc[u]]; 把空子树当作满二叉树 不这样写就要给叶子单独开分支,代码多一层
h[u] = max(hl, hr) + 1; 求子树高度 高度由较长的那一侧决定;只有左孩子时 = hl + 1
if (hl == hr) cmpl[u] = fl && cr; 等高时判完全 两侧等高 ⇒ 最后一层从右子树开始收尾,所以左子树必须是满的,右子树只需完全
else if (hl == hr+1) cmpl[u] = cl && fr; 左高一时的完全条件 最后一层落在左子树里 ⇒ 左子树可以是"不完全但规整"的,右子树必须是满的
else cmpl[u] = false; 其余情况判假 右边比左边高,或高度差 ≥ 2 ⇒ 中间一定有空档,不可能完全
🧠
怎么记住这两个条件?画一下就知道:完全二叉树是"从左往右依次填"。 如果左右一样高,说明右边这一层也开始了,那左边就必须已经填满; 如果左边比右边高一层,说明最后一层只在左边还没填完,所以左边允许"不完全",右边必须是"满"。

⚠️ 递归深度陷阱与迭代写法

题目没有保证树是平衡的。如果输入是一条长链(1→2→3→…→n),递归深度会达到 10⁵, C++ 默认栈空间通常只有 1~8 MB,很容易栈溢出(RE)。

有两种改法,推荐第二种(不依赖编译选项):

// 写法一:手动扩栈(Windows / 部分评测机有效)
// 在 main 开头加:#pragma comment(linker, "/STACK:268435456")
// 在 Linux 下则要编译时加 -Wl,--stack=268435456,不可控,不推荐

// 写法二(推荐):迭代求逆前序,等价于后序
vector<int> order;
stack<int> st;
st.push(1);
while (!st.empty()) {
    int u = st.top(); st.pop();
    if (u == 0) continue;
    order.push_back(u);          // 前序:父在子之前
    st.push(lc[u]);
    st.push(rc[u]);
}
// 逆序处理 ⇒ 每个结点被处理时,孩子早已算完
for (int i = (int)order.size() - 1; i >= 0; i--) {
    int u = order[i];
    // ... 与递归版完全相同的合并逻辑 ...
}
⚠️
为什么"逆前序"就是"后序"?在前序遍历里,父结点一定排在它的所有后代之前; 把序列倒过来,后代就排到了父结点之前,于是每个结点被处理时,左右孩子必然已经算完。这就是它的正确性依据。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

输入树形答案考察点
1
0 0
单结点 1 最小规模,叶子必然是
2
2 0
0 0
只有左孩子 2 只有左孩子 ⇒ 仍然是完全二叉树
2
0 2
0 0
只有右孩子 1 坑!根不完全,只有结点 2 贡献 1 棵
3
2 3
0 0
0 0
3 结点满二叉树 3 满 ⇒ 完全,每层都贡献
7
2 3
4 5
6 7
0 0
0 0
0 0
0 0
7 结点完美二叉树 7 所有子树都是满的
4
2 3
0 0
4 0
0 0
样例 2 3 右边比左边高 ⇒ 根不完全
5
2 0
3 0
4 0
5 0
0 0
5 结点左链 2 反直觉:只有最后两个结点是完全的,详见下方
100000 的左链 深度 10⁵ — 递归会爆栈,必须改迭代

🔍 为什么"左链"只有 2 棵完全?

左链 1→2→3→4→5(全是左孩子)看着很"整齐",但完全二叉树不是这么定义的:

✓
结点 5(叶子)与结点 4

结点 5:叶子,完全 ✓

结点 4:hl = 1、hr = 0 → 满足 hl = hr+1 → 完全 ✓

已得 2 棵

✗
结点 3(子树 3→4→5)

hl = h_4 = 2、hr = 0

hl = hr?否。hl = hr+1?2 ≠ 1,也否

→ 完全 = 假

直观理解:一棵 3 个结点的完全二叉树应该是 根 + 左 + 右(第二层放满), 而这里第二层只有左孩子、右边空着,最后一层的结点没有"从最左边开始紧挨着排"。

✗
结点 2、结点 1

同理,高度差都超过 1,全部判假。

📌
结论:"看起来像链"的树,只有最底下两个结点能贡献完全子树。 这个例子说明:不能靠直觉判断,必须老老实实按高度差分类讨论。

🚨 易错点清单

❌
错误 1:把"满"和"完全"当成一回事
满二叉树(2^h-1 个结点)一定是完全二叉树,但完全二叉树远不止满二叉树。 样例 2 里的结点 3(只有左孩子)就是"完全但不满"的典型例子。
❌
错误 2:忘了空子树的约定
若不在读入时把空孩子统一视为"高度 0、满、完全",就会出现叶子结点漏计、 或 h[0] 取到随机值导致高度算错。
❌
错误 3:以为孩子编号一定大于父结点
题目没有这个保证。所以不能简单地"从 n 到 1 倒着算", 必须先真正遍历出树上的顺序(或用递归 / 显式栈)。
❌
错误 4:递归爆栈
链状数据下递归深度可达 10^5,必须改迭代(逆前序)或确认评测机栈空间足够。 这是本题最容易"本地能过、评测 RE"的地方。
❌
错误 5:只判断整棵树,忘了数 n 棵
答案的统计对象是每个结点各自的子树,计数要放在每个结点的合并逻辑里, 而不是最后对根结点判断一次。
09
复杂度分析
每个结点只算一次

📊 复杂度四宫格

时间复杂度
O(n)
空间复杂度
O(n)
n 最大
10⁵
结点访问次数
n 次

时间为什么是 O(n)?

空间都用在哪?

用途大小说明
lc[]、rc[]O(n)存左右孩子
h[]、full[]、cmpl[]O(n)每个结点的三个状态量
递归调用栈O(h)最好 O(log n),最坏(链)O(n)
迭代版额外栈O(n)用显式栈换取不爆栈

✅ n = 10⁵ 时总操作约 10⁵ 次,C++ 不到 1 毫秒,稳过满分。

10
知识拓展
学一道题,会一类题

🔗 二叉树常考公式小抄

// 满二叉树:高度 h ⇒ 结点数 = 2^h - 1
int fullNodes(int h) { return (1 << h) - 1; }

// 完全二叉树用"数组编号"看孩子(堆的性质)
// 下标从 1 开始:结点 i 的左孩子 2i,右孩子 2i+1
// 下标从 0 开始:结点 i 的左孩子 2i+1,右孩子 2i+2

// 判断"数组编号 = 结点编号"的情形下是否完全:
// 只需找第一个"有右孩子却没有左孩子"的结点
bool isComplete(int n) {
    for (int i = 1; i <= n; i++) {
        if (2*i+1 <= n && 2*i > n) return false;
    }
    return true;
}

// 树形 DP 通用套路:把"子树的答案"当返回值往上传递

🌟 举一反三

这道题训练的是"树形 DP + 边界约定",把这两块能力迁移出去,很多题都能拆解。

能力点本题怎么用还能迁移到
后序遍历先算孩子再算自己,保证合并时信息齐全树的重心、子树和、树形背包
状态三元组用一个结点的 (高度, 满, 完全) 描述整棵子树树上计数、方案数、最大独立集
空值约定空子树 = 高度 0 + 满 + 完全任何递归 DP 的边界处理
高度差分类讨论把 3 种情况穷尽,避免遗漏平衡树判定、AVL 旋转条件
🌟
思考题: ① 如果把问题改成"统计满二叉树子树的数量",三元组里的判定该怎么改?提示:判定条件会简单很多——不再需要区分"完全"。
② 如果题目不保证根是 1 号结点(例如只给 n 行孩子信息),你要怎么找出根? 提示:统计每个结点的"入度",入度为 0 的那个就是根。