统计给定的 n 棵子树中,有多少棵是满二叉树(完美二叉树)。
给定一棵 n 个结点的有根二叉树(根为 1),结点 i 的左右儿子为 lᵢ、rᵢ(不存在则为 0)。求所有 n 棵子树中各有多少棵是满二叉树。
满二叉树指:所有叶子深度相同,且除叶子外每个结点都有两个儿子。
完美二叉树两状态树形 DP自底向上避免递归爆栈
| 项目 | 说明 |
|---|---|
| 输入 | n;随后 n 行,每行 lᵢ、rᵢ |
| 输出 | 所有子树中满二叉树的个数 |
| 数据范围 | 1 ≤ n ≤ 10⁵ |
| 标记 | 儿子不存在时编号为 0 |
| 判定 | 叶子深度相同 + 非叶子都有两个儿子 |
ok[u](是否完美)与 h[u](高度)结构:1 的左儿子 2、右儿子 3;2 只有左儿子 4;3、4 都是叶子。
| 结点 | l | r | 子树形状 | 是否完美 | 高度 |
|---|---|---|---|---|---|
| 4 | 0 | 0 | 单结点 | ✓ | 1 |
| 3 | 0 | 0 | 单结点 | ✓ | 1 |
| 2 | 4 | 0 | 只有左孩子 | ✗ | 2 |
| 1 | 2 | 3 | 左子树不完美 | ✗ | 3 |
完美子树共 2 棵(结点 3、4)✓
它只有左儿子 4,没有右儿子
"除叶子外每个结点都要有两个儿子"——结点 2 不是叶子,却只有一个儿子
所以判定为不完美
✗ 结点 2 不完美
它的左儿子 2 的子树不完美
而且左右子树高度也不同(左边高 2,右边高 1)
两个条件都不满足
所以不完美
✗ 结点 1 不完美
这是最"完美"的情形:1 有两个叶子儿子。
| 结点 | l | r | 是否完美 | 高度 | 说明 |
|---|---|---|---|---|---|
| 2 | 0 | 0 | ✓ | 1 | 叶子 |
| 3 | 0 | 0 | ✓ | 1 | 叶子 |
| 1 | 2 | 3 | ✓ | 2 | 两个孩子都是完美且高度相同 → 完美 |
完美子树共 3 棵 ✓(整棵树 + 两个叶子)
| 左右子树高度关系 | 是否完美 |
|---|---|
| 都不存在(叶子) | ✓ 完美 |
| 都完美且高度相同 | ✓ 完美 |
| 都完美但高度不同 | ✗ 不完美 |
| 有一个不完美 | ✗ 不完美 |
| 只有一个儿子 | ✗ 不完美 |
lᵢ、rᵢ,儿子的编号不一定大于 i(比如结点 1 的儿子是 5 和 2)。每个结点维护 (是否完美, 高度),自底向上合并
ok = ok[left] && ok[right] && h[left] == h[right];h = h[left] + 1。注意左右儿子必须都存在,否则直接判假。枚举 n 个根,各自 DFS 检查所有叶子深度与儿子数
ok[u]、h[u],就把 O(n²) 压到了 O(n)。| 方案 | 复杂度 | 可行性 |
|---|---|---|
| 两状态 DP | O(n) | ✅ 稳过 |
| 逐子树判定 | O(n²) | ❌ 超时 |
第一行输入 n,随后 n 行输入每个结点的左右儿子编号。
点按钮开始 →
#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 | 高度 | 父亲比儿子高一层 |
写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
4 | 2 | 题面样例 1(结点 3、4 是完美子树) |
3 | 3 | 题面样例 2(整棵树 + 两个叶子) |
1 | 1 | 只有一个结点,它自己是完美子树 |
7 | 7 | 三层完美二叉树,7 棵子树全完美 |
5 | 2 | 结点 2 只有左儿子;结点 5 孤立(不连通) |
左右儿子数组、ok 与高度数组、后序栈,均为 O(n)。
✅ 约 10 万次操作,瞬间完成。关键是"把子树判定结果缓存下来复用",避免 O(n²)。
// 完美(满)二叉树的判定 // 叶子:完美,高度 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 大且形状可能是链时 |