给定一棵 n 个结点的有根二叉树,每个结点的左右儿子都已给出,
请统计所有 n 棵子树里,有多少棵是完全二叉树。
给定一棵包含 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=4,输入只差一行,但答案分别是 4 和 3。区别就在结点 2 和结点 3 谁有孩子。
我们用"后序"的顺序(先孩子、后自己)逐个结点算,每一步都记录三个量:高度 h、是否满 full、是否完全 cmpl。
左右孩子都是 0。按约定空子树 h=0、满=真、完全=真。
于是 h₂ = (0,0)+1 = 1;hl=hr=0 → 满 = 真,完全 = 左满 ∧ 右完全 = 真
✅ 完全 → 计数 1
同样是叶子:h₄ = 1,满 = 真,完全 = 真。
✅ 完全 → 计数 2
取 h₄ = 1、右孩子为空 h=0 → hl = 1, hr = 0
满足 hl = hr + 1 → 完全 = 完全左 ∧ 满右 = 真 ∧ 真(空子树) = 真
h₃ = (1,0)+1 = 2;因为 hl ≠ hr,所以满 = 假
✅ 完全 → 计数 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 · 0 | 1 | 是 | ✅ 是 | 1 |
| 4 | — · — | 0 · 0 | 1 | 是 | ✅ 是 | 2 |
| 3 | 4 · — | 1 · 0 | 2 | 否 | ✅ 是 | 3 |
| 1 | 2 · 3 | 1 · 2 | 3 | 否 | ❌ 否 | 3 |
最终答案:3 棵 ✓
这是本题最容易记混的一点,用"层序排列"的视角看就很清楚:
| 情形 | 层序展开图 | 是否完全 | 原因 |
|---|---|---|---|
| 只有左孩子 | 父 → 左(左边填满,右边空着) |
✅ 是 | 最后一层的结点仍然"靠左排" |
| 只有右孩子 | 父 → 空 → 右(中间挖了个洞) |
❌ 否 | 右边的位置被占了,左边却空着,不满足"靠左" |
hl = 0、hr ≥ 1,
既不可能满足 hl = hr,也不可能满足 hl = hr + 1,
所以自动落入"其他情况 → 完全 = 假"。公式天然处理了这个坑,不用特判。
对每个结点,用它自己为根做一次 BFS,检查是否出现"空孩子之后又出现非空孩子"
每个结点只算一次,把 (高度, 是否满, 是否完全) 直接交给父结点用
| n 的规模 | 逐棵判定(O(n²)) | 后序 DP(O(n)) | 现实结果 |
|---|---|---|---|
| 500(40% 测试点) | 约 12 万次 | 约 500 次 | 两者都能过 |
| 10,000 | 约 5×10⁷ 次 | 约 10⁴ 次 | 尚可,已偏慢 |
| 100,000(满分要求) | 约 5×10⁹ 次 | 约 10⁵ 次 | 暴力超时,DP 稳过 |
如果我们规定空子树的高度为 0、是满二叉树、也是完全二叉树,那么叶子结点就不用单独写分支了:
| 结点类型 | hl · hr | 套用公式 | 结果 |
|---|---|---|---|
| 叶子(左右皆空) | 0 · 0 | hl == hr → 满 = 满L ∧ 满R;完全 = 满L ∧ 完全R |
满 = 真,完全 = 真,h = 1 ✓ |
if (是叶子) 的特判。
统一约定边界值,代码的分支数就少一层,出错概率也低——这是树形 DP 里非常常用的技巧。
第一行输入结点数 n,接下来 n 行每行两个数表示左、右孩子编号(不存在填 0)。
点"算一下"按钮开始 →
#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]; // ... 与递归版完全相同的合并逻辑 ... }
| 输入 | 树形 | 答案 | 考察点 |
|---|---|---|---|
1 |
单结点 | 1 | 最小规模,叶子必然是 |
2 |
只有左孩子 | 2 | 只有左孩子 ⇒ 仍然是完全二叉树 |
2 |
只有右孩子 | 1 | 坑!根不完全,只有结点 2 贡献 1 棵 |
3 |
3 结点满二叉树 | 3 | 满 ⇒ 完全,每层都贡献 |
7 |
7 结点完美二叉树 | 7 | 所有子树都是满的 |
4 |
样例 2 | 3 | 右边比左边高 ⇒ 根不完全 |
5 |
5 结点左链 | 2 | 反直觉:只有最后两个结点是完全的,详见下方 |
100000 的左链 |
深度 10⁵ | — | 递归会爆栈,必须改迭代 |
左链 1→2→3→4→5(全是左孩子)看着很"整齐",但完全二叉树不是这么定义的:
结点 5:叶子,完全 ✓
结点 4:hl = 1、hr = 0 → 满足 hl = hr+1 → 完全 ✓
已得 2 棵
hl = h_4 = 2、hr = 0
hl = hr?否。hl = hr+1?2 ≠ 1,也否
→ 完全 = 假
直观理解:一棵 3 个结点的完全二叉树应该是 根 + 左 + 右(第二层放满),
而这里第二层只有左孩子、右边空着,最后一层的结点没有"从最左边开始紧挨着排"。
同理,高度差都超过 1,全部判假。
2^h-1 个结点)一定是完全二叉树,但完全二叉树远不止满二叉树。
样例 2 里的结点 3(只有左孩子)就是"完全但不满"的典型例子。
h[0] 取到随机值导致高度算错。
10^5,必须改迭代(逆前序)或确认评测机栈空间足够。
这是本题最容易"本地能过、评测 RE"的地方。
max、两个 if 判断| 用途 | 大小 | 说明 |
|---|---|---|
lc[]、rc[] | O(n) | 存左右孩子 |
h[]、full[]、cmpl[] | O(n) | 每个结点的三个状态量 |
| 递归调用栈 | O(h) | 最好 O(log n),最坏(链)O(n) |
| 迭代版额外栈 | O(n) | 用显式栈换取不爆栈 |
✅ n = 10⁵ 时总操作约 10⁵ 次,C++ 不到 1 毫秒,稳过满分。
// 满二叉树:高度 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 旋转条件 |