🌳 完全二叉树子树计数

1. 题目 2. 什么是完全二叉树 3. 六种情况 4. 算法动画 5. 代码 6. 样例推演 7. 测验

📖 第一关：题目解读

题目大意：给定一棵 n 个节点的有根二叉树（根为 1）。每个节点有左儿子 l_i 和右儿子 r_i（0 表示不存在）。对每个节点，以它为根的子树是不是「完全二叉树」？一共有多少棵子树是完全二叉树？

输入：第一行 n；接下来 n 行，每行 l_i r_i
输出：一个整数，完全二叉树子树的数量
数据范围：n ≤ 10⁵，时间 1s

🔍 翻译成人话：树上有 n 个节点，每个节点往下看都是一棵子树。问这 n 棵子树里，有几棵是「完全二叉树」。
注意：是所有 n 棵子树都算，不只是根的那一棵！

样例 1

1的左右=2,3；2的左=4；3、4是叶子

节点	子树完全？
4	是
3	是
2	是
1	是

答案 = 4

样例 2

1的左右=2,3；3的左=4；2、4是叶子

节点	子树完全？
4	是
2	是
3	是
1	否

答案 = 3

⚠️ 为什么暴力 O(n²) 不行？
对每个节点单独判断子树是否完全，每次 O(size)，总和 O(n²)。n=10⁵ 时 = 10¹⁰，1 秒跑不完 → TLE。
需要 O(n) 的方法：一次后序遍历搞定所有节点。

🌲 第二关：什么是「完全二叉树」？

做这道题，必须先分清三种二叉树：普通二叉树、完全二叉树、满二叉树。它们是层层递进的关系。

普通二叉树

随便长，没有限制

完全二叉树

除最后一层全满，最后一层从左到右连续

满二叉树（完美满）

每一层都全满，没有任何空缺

🎯 关键关系：
满二叉树 ⊂ 完全二叉树 ⊂ 二叉树
• 满：每一层都全满（节点数 = 2^(h+1) - 1）
• 完全：除最后一层全满，最后一层从左到右连续（中间不能空）
• 满一定完全，但完全不一定满

💡 形象记忆：完全二叉树就像一栋楼，从底到顶每层都住满人，只有最顶层可以没住满，而且最顶层的人必须从左往右挨着住，不能跳着住。如果顶层左边空着右边有人，就不完全！

🔧 第三关：六种情况分类

这是本题的核心。我们要对每个节点判断「以它为根的子树是否完全」。关键思路：后序遍历，先算左右子，再根据左右子的信息推出当前节点。每个节点要带三个信息向上汇报：

每个节点向上汇报三样东西：
① isComp：我的子树是不是完全二叉树？
② isFull：我的子树是不是满二叉树（每层全满）？
③ height：我的子树高度是多少？（空节点高度 = -1，叶子高度 = 0）

为什么要 isFull？因为父节点判断时，需要知道我的子树是不是「最后一层全满」——这正是 isFull 的含义！

设左子返回 (cL, fL, hL)，右子返回 (cR, fR, hR)，根据左右高度关系分六种情况：

✅ 情况 1：左右都空（叶子节点）

hL = hR = -1 → 是叶子。完全 ✓ 且满 ✓，高度 0。每个叶子都算一棵完全二叉树。

✅ 情况 2：只有左子，右子空，且左子是叶子

hL = 0, hR = -1 → hL = hR + 1。左子必须完全（叶子天然完全），右子空天然满。完全 ✓（不满，因为最后一层没满）。高度 1。

注意：只有左子时，左子必须是叶子（高度0）。如果左子高度 ≥1，就不完全。

❌ 情况 3：只有右子，左子空

完全二叉树不可能「有右子没左子」（最底层必须从左到右连续，左边空了右边不能有）。不完全 ✗。

✅ 情况 4：左右都有，左右等高，且左子满、右子完全

hL = hR 且 fL && cR → 左子树每层全满，右子树从最左开始连续填充（允许最后一层不满）→ 完全 ✓，高度 hL+1。若右子也满（fL && fR）则同时是满二叉树！

✅ 情况 5：左右都有，左比右高一层，左完全且右满

hL = hR + 1。右子必须满（右子最后一层全满），左子必须完全。这样最后一层的节点全在左子，且从左到右连续。完全 ✓（不满）。高度 hL+1。

❌ 情况 6：其他（高度差>1 或右比左高或等高但左子不满 / 右子不完全）

hL 和 hR 的差不是 0 也不是 1（左比右多2层以上，或右比左高），或者等高但左子不满 / 右子不完全 → 不完全 ✗。

🎯 一句话总结判定逻辑：
if (hL == hR) comp = fL && cR;　（等高→左满、右完全）
else if (hL == hR + 1) comp = cL && fR;　（左高一层→左完全右满）
else comp = false;　（其他都不行）

🎬 第四关：算法执行动画

用一棵 8 节点的教学树演示后序遍历全过程。每个节点处理时会显示它收到左右子的三状态信息，然后判定自己是否完全。

未处理

完全 ✓

不完全 ✗

当前处理

点击「播放」开始后序遍历动画

完全二叉树数：0

当前步：0

速度：中速

👀 观察重点：
• 后序遍历 = 先左子、再右子、最后根（自底向上）
• 叶子节点（7、8、5）最先处理，都是完全 ✓
• 节点 4 只有左子 7（叶子）→ 完全 ✓（情况2）
• 节点 6 只有右子 8 → 不完全 ✗（情况3）
• 节点 2 左4右5，hL=1=hR+1，左完全右满 → 完全 ✓（情况5）
• 节点 3 左空右6（不完全）→ 不完全 ✗
• 节点 1 左2右3，hL=2=hR 但都不满 → 不完全 ✗（情况6）
最终答案 = 5（节点 7,8,4,5,2）

💻 第五关：C++ 代码逐行讲解

📄 点击展开完整 AC 代码 ▶

/*
 * 完全二叉树子树计数
 * 后序遍历,每个节点返回(isComp, isFull, height)
 * 空节点: (true, true, -1)
 * 时间 O(n)
 */
#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
int lc[N], rc[N];  // 左右儿子,0=空
int ans = 0;

// 返回 {isComp, isFull, height}
tuple<bool,bool,int> dfs(int u) {
    if (u == 0)
        return {true, true, -1};  // 空节点
    
    auto [cL, fL, hL] = dfs(lc[u]);
    auto [cR, fR, hR] = dfs(rc[u]);
    
    bool comp, full;
    int h;
    
    if (hL == hR) {              // 情况4: 等高 → 左满、右完全
        comp = fL && cR;        // 等高: 左子树满 + 右子树完全
        full = fL && fR;
        h = hL + 1;
    } else if (hL == hR + 1) {  // 情况5: 左高一层
        comp = cL && fR;        // 左完全, 右满
        full = false;
        h = hL + 1;
    } else {                     // 情况6: 其他
        comp = false;
        full = false;
        h = max(hL, hR) + 1;
    }
    
    if (comp) ans++;  // 统计完全二叉树
    return {comp, full, h};
}

int main() {
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> lc[i] >> rc[i];
    dfs(1);
    cout << ans << endl;
    return 0;
}

🔑 关键点逐个拆解

第 1 点：为什么要返回三个值？
isComp：直接回答题目（这棵子树完全吗？）。
isFull：父节点判断时需要——如果父节点左右等高，要求左子满；如果父节点左比右高一层，要求右子满。没有 isFull，父节点没法判断。
height：判断高度关系（等高？差一层？差太多？）必须用高度。

第 2 点：空节点为什么返回 (true, true, -1)？
空节点是一棵「空树」，空树既是完全的也是满的（没有任何违规），高度 -1（比叶子矮一层）。
这样叶子节点（左右都空）：hL=hR=-1 → 等高分支 → comp = fL&&cR = true&&true = true → 完全且满，高度 0。✓ 一行代码搞定叶子！

第 3 点：为什么用后序遍历？
判断节点 u 是否完全，需要先知道左右子是否完全/满/高度。所以必须先递归左右子，再处理 u——这就是后序。一次遍历算完所有 n 个节点，O(n)。

第 4 点：n=10⁵ 会不会爆栈？
最坏情况树是一条链（每个节点只有右子），递归深度 = n = 10⁵。默认栈可能不够。考场可以：
• 编译加 -Wl,-stack_size,0x1000000（macOS）或开大栈
• 或改写成迭代后序遍历
GESP 评测机一般默认栈够大，但留个心眼。

🎬 第六关：样例推演

样例 1：答案 = 4

处理顺序	节点	左子(cL,fL,hL)	右子(cR,fR,hR)	情况	结果(comp,full,h)	计数
1	4	空(T,T,-1)	空(T,T,-1)	叶子(等高)	(T,T,0)	1
2	2	4(T,T,0)	空(T,T,-1)	左高一层	(T,F,1)	2
3	3	空(T,T,-1)	空(T,T,-1)	叶子(等高)	(T,T,0)	3
4	1	2(T,F,1)	3(T,T,0)	左高一层	(T,F,2)	4

输出：4 ✅

样例 2：答案 = 3

处理顺序	节点	左子(cL,fL,hL)	右子(cR,fR,hR)	情况	结果(comp,full,h)	计数
1	2	空(T,T,-1)	空(T,T,-1)	叶子	(T,T,0)	1
2	4	空(T,T,-1)	空(T,T,-1)	叶子	(T,T,0)	2
3	3	4(T,T,0)	空(T,T,-1)	左高一层	(T,F,1)	3
4	1	2(T,T,0)	3(T,F,1)	右比左高!	(F,F,2)	3

输出：3 ✅ 节点1的右子比左子高 → 不完全

💡 对比两个样例的差别：
样例1：节点1的左子高度=1，右子高度=0，左比右高一层 → 完全
样例2：节点1的左子高度=0，右子高度=1，右比左高 → 不完全！
完全二叉树只允许左比右高，不能右比左高。

🎯 第七关：互动测验

7 道题，检验你对完全二叉树和算法的理解。