GESP 题解库 / 6 级题解 / [GESP202606 六级] 满二叉树 · 第 25 / 27 题
GESP202606 六级 · · 中等

满二叉树

统计给定的 n 棵子树中,有多少棵是满二叉树(完美二叉树)。

📊
n ≤ 10⁵
结点数量
🔢
long long
计数结果
⚡
O(n)
时间复杂度
🎯
自底向上两状态树形 DP
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

给定一棵 n 个结点的有根二叉树(根为 1),结点 i 的左右儿子为 lᵢ、rᵢ(不存在则为 0)。求所有 n 棵子树中各有多少棵是满二叉树。

满二叉树指:所有叶子深度相同,且除叶子外每个结点都有两个儿子。

💡
人话翻译:这里的"满二叉树"就是完美二叉树(每层都排满)。
判定方法很自然:从叶子往上两两合并——一个结点是完美二叉树,当且仅当它有两个儿子,且两个儿子的子树都是完美二叉树、且高度相同。
于是只需对每个结点记录"是否完美"和"高度"两个信息,自底向上一遍即可,O(n)。

🔍 关键词提取

完美二叉树两状态树形 DP自底向上避免递归爆栈

已知条件

项目说明
输入n;随后 n 行,每行 lᵢ、rᵢ
输出所有子树中满二叉树的个数
数据范围1 ≤ n ≤ 10⁵
标记儿子不存在时编号为 0
判定叶子深度相同 + 非叶子都有两个儿子

需要解决的问题

02
思维导图
整理解题思路的全貌
🌲 ok[u] 与 h[u] 两个信息
🍃 叶子
两个儿子都是 0
ok = 真(单结点是完美二叉树)
h = 1
这是递归基
🌲 内部结点
必须两个儿子都存在
且两个子树都 ok
且高度相同 h[left] == h[right]
则 ok = 真,h = 高度 + 1
❌ 不完美的情况
只有一个儿子
某个子树不完美
两个子树高度不同
满足任一即 ok = 假
⚠️ 易错点
用编号顺序递推(儿子编号不一定更大)
递归导致爆栈
只有一个儿子时误判为完美
忘记计数叶子
03
样例手算推导
两个样例的完整推演

🧮 样例 1:n = 4,儿子为 (2,3)、(4,0)、(0,0)、(0,0)

结构:1 的左儿子 2、右儿子 3;2 只有左儿子 4;3、4 都是叶子。

结点lr子树形状是否完美高度
400单结点✓1
300单结点✓1
240只有左孩子✗2
123左子树不完美✗3

完美子树共 2 棵(结点 3、4)✓

1
为什么结点 2 不是完美?

它只有左儿子 4,没有右儿子

"除叶子外每个结点都要有两个儿子"——结点 2 不是叶子,却只有一个儿子

所以判定为不完美

✗ 结点 2 不完美

2
为什么结点 1 不是完美?

它的左儿子 2 的子树不完美

而且左右子树高度也不同(左边高 2,右边高 1)

两个条件都不满足

所以不完美

✗ 结点 1 不完美

🔑
注意"单个叶子也是满二叉树":题目样例说明明确写了"包括整个树本身,及所有的单个叶子节点"。
所以每棵叶子子树都算 1 棵完美子树——这也是为什么样例 2 的答案恰好等于 n。

🧮 样例 2:n = 3,儿子为 (2,3)、(0,0)、(0,0)

这是最"完美"的情形:1 有两个叶子儿子。

结点lr是否完美高度说明
200✓1叶子
300✓1叶子
123✓2两个孩子都是完美且高度相同 → 完美

完美子树共 3 棵 ✓(整棵树 + 两个叶子)

📊 高度与完美性的对照

左右子树高度关系是否完美
都不存在(叶子)✓ 完美
都完美且高度相同✓ 完美
都完美但高度不同✗ 不完美
有一个不完美✗ 不完美
只有一个儿子✗ 不完美
⚠️
关于处理顺序的一个重要提醒:题目给的是 lᵢ、rᵢ,儿子的编号不一定大于 i(比如结点 1 的儿子是 5 和 2)。
所以不能简单地"从 n 倒着算到 1",必须按树的后序拓扑顺序处理(先算出所有儿子再算父亲)。实现时可以先从根做一次迭代 DFS 求出后序,再逆序计算。
04
解法对比
自底向上树形 DP vs 逐个子树暴力判定

⚔️ 解法对比

🟢 两状态树形 DP(推荐) 推荐

每个结点维护 (是否完美, 高度),自底向上合并

  • 时间 O(n)
  • n = 10⁵ 时约 10⁵
  • 代码 35 行(迭代版)
  • 空间 O(n)
💡
合并规则:ok = ok[left] && ok[right] && h[left] == h[right];h = h[left] + 1。注意左右儿子必须都存在,否则直接判假。

🟠 对每棵子树单独判定

枚举 n 个根,各自 DFS 检查所有叶子深度与儿子数

  • 每棵子树 O(子树大小)
  • 总计最坏 O(n²) = 10¹⁰
  • 必然超时
  • 只能过 n ≤ 500 的测试点
⚠️
为什么要复用:同一棵子树会在"自己作为根"和"作为父结点的一部分"时被重复检查很多次。把结果缓存成 ok[u]、h[u],就把 O(n²) 压到了 O(n)。

📈 性能对比

方案复杂度可行性
两状态 DPO(n)✅ 稳过
逐子树判定O(n²)❌ 超时
05
算法流程图
按后序自底向上合并
开始读入 n 与每个结点的左右儿子 l[i]、r[i]从根 1 出发做迭代 DFS,得到后序序列 order按后序(儿子在前)依次处理每个结点 uu 的两个儿子是否都存在?是 ✓检查两子树否 ✗若两个都不存在则 ok=真、h=1;否则 ok=假ok = ok[l] 且 ok[r] 且 h[l] == h[r];h = h[l] + 1若 ok 为真则答案加 1输出答案处理下一个结点
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🌲 满二叉树计数

第一行输入 n,随后 n 行输入每个结点的左右儿子编号。

结果会显示在这里

点按钮开始 →

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

💻 完整 C++ 代码(迭代后序,避免爆栈)

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

int lc[100005], rc[100005];
bool ok[100005];
int hgt[100005];
vector<int> order;

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d %d", &lc[i], &rc[i]);

    // 迭代求后序:先左、再右、最后自己
    vector<pair<int,int>> st;        // (结点, 阶段)
    vector<bool> seen(n + 1, false);
    st.push_back({1, 0});
    seen[1] = true;
    while (!st.empty()) {
        pair<int,int> &top = st.back();
        int u = top.first;
        if (top.second == 0) {
            top.second = 1;
            if (lc[u] && !seen[lc[u]]) { seen[lc[u]] = true; st.push_back({lc[u], 0}); continue; }
        }
        if (top.second <= 1) {
            top.second = 2;
            if (rc[u] && !seen[rc[u]]) { seen[rc[u]] = true; st.push_back({rc[u], 0}); continue; }
        }
        order.push_back(u);
        st.pop_back();
    }

    long long ans = 0;
    for (int u : order) {                       // 后序:儿子一定在父亲前面
        if (lc[u] == 0 && rc[u] == 0) {         // 叶子
            ok[u] = true; hgt[u] = 1;
        } else if (lc[u] == 0 || rc[u] == 0) {  // 只有一个儿子
            ok[u] = false;
            hgt[u] = 1 + (lc[u] ? hgt[lc[u]] : hgt[rc[u]]);
        } else {                                // 两个儿子都有
            ok[u] = ok[lc[u]] && ok[rc[u]] && (hgt[lc[u]] == hgt[rc[u]]);
            hgt[u] = hgt[lc[u]] + 1;
        }
        if (ok[u]) ans++;
    }

    printf("%lld\n", ans);
    return 0;
}
🔑
为什么"高度相同"这个条件就够了?因为我们是递归判定的:左右子树各自都已经是完美二叉树(内部所有叶子深度相同),此时只要两边高度相同,那么整棵树的叶子就都落在同一层——"所有叶子深度相同"这个条件自动满足。
这就是"把两个条件合并成一个递归判定"的关键。

📖 关键几行怎么看

代码作用为什么这样写
迭代后序确定处理顺序儿子编号不一定更大,不能按编号倒推
lc[u]==0 && rc[u]==0叶子单结点是完美二叉树
lc[u]==0 || rc[u]==0单儿子不满足"两个儿子"直接判假
ok[l] && ok[r] && hgt[l]==hgt[r]合并两个子树都完美且等高
hgt[u] = hgt[l] + 1高度父亲比儿子高一层
⚠️
四个坑:① 按编号从 n 到 1 递推(儿子编号可能更大,会用到未计算的值);② 递归 DFS(n 可达 10⁵,链状数据会爆栈);③ 只有一个儿子时误判为完美;④ 只比较高度而忘记检查两子树自身是否完美。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
4
2 3
4 0
0 0
0 0
2题面样例 1(结点 3、4 是完美子树)
3
2 3
0 0
0 0
3题面样例 2(整棵树 + 两个叶子)
1
0 0
1只有一个结点,它自己是完美子树
7
2 3
4 5
6 7
0 0
0 0
0 0
0 0
7三层完美二叉树,7 棵子树全完美
5
2 3
4 0
0 0
0 0
0 0
2结点 2 只有左儿子;结点 5 孤立(不连通)
✅
自查清单:① 按后序处理吗?② 检查了两个儿子都存在吗?③ 高度和完美性都比了吗?

🚨 易错点清单

⚠️
按编号倒推:儿子编号可能大于父亲,必须按后序处理。
⚠️
递归爆栈:n = 10⁵ 且可能是链,要用迭代后序。
⚠️
漏判"只有一个儿子":这种情况一定不完美。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(n)
空间复杂度
O(n)
n 最大
10⁵
运算量
约 10⁵

时间怎么算的?

空间都用在哪?

左右儿子数组、ok 与高度数组、后序栈,均为 O(n)。

✅ 约 10 万次操作,瞬间完成。关键是"把子树判定结果缓存下来复用",避免 O(n²)。

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

🔗 常用技巧小抄

// 完美(满)二叉树的判定
// 叶子:完美,高度 1
// 内部:两个儿子都存在 && 两个子树都完美 && 高度相同

// 迭代后序模板(儿子编号任意)
vector<pair<int,int>> st;      // (结点, 阶段) 0=未处理 1=已入左 2=已入右
st.push_back({root, 0});
while (!st.empty()) {
    auto &t = st.back();
    int u = t.first;
    if (t.second == 0) { t.second = 1; if (lc[u]) { st.push_back({lc[u],0}); continue; } }
    if (t.second <= 1) { t.second = 2; if (rc[u]) { st.push_back({rc[u],0}); continue; } }
    order.push_back(u); st.pop_back();
}
// order 即为后序(儿子在父亲之前)

// 对照:如果是"完全二叉树"判定(允许最后一层不满)
// 需要记录 (是否完全, 高度, 是否满) 三个信息
// 本题问"满",所以两个信息就够

// 若题目保证 l_i, r_i 都大于 i,则可直接从 n 倒着算,代码更短

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
后序树形 DP先儿子后父亲所有需要子树信息的树题
两状态缓存把结果存下来复用避免 O(n²) 的重复计算
迭代代替递归手动栈n 大且形状可能是链时
🌟
思考题:如果题目改成"统计完全二叉树的子树个数"(最后一层可以不满,但必须从左到右连续),状态要怎么改?(提示:需要三个信息——"是否满"、"是否完全"、"高度",因为"左满右完全"这种组合也构成完全二叉树。判定条件越复杂,需要的状态就越多——这正是树形 DP 设计状态的通用规律。)