完全二叉子树计数

第零课

题目解读

给定一棵有根二叉树（根为 1），每个节点有左右儿子。问：所有 n 棵子树中，有多少棵是完全二叉树？

输入输出格式

输入：第一行 n，接下来 n 行每行两个整数 l_i, r_i（0 表示无此儿子）。

输出：一个整数——完全二叉子树的数量。

样例 1

n=4。节点 1→(2,3)，2→(4,0)，3→(0,0)，4→(0,0)。所有 4 棵子树都是完全二叉树，答案 = 4。

样例 2

n=4。节点 1→(2,3)，2→(0,0)，3→(4,0)，4→(0,0)。只有节点 1 的子树不是完全二叉树，答案 = 3。

核心问题

对每个节点 u，判断以 u 为根的子树是否是完全二叉树。朴素做法是对每棵子树单独检查，但那样是 O(n²)。我们要找一种 O(n) 的方法——一次 DFS 搞定所有节点。

第一课

什么是完全二叉树？

完全二叉树是二叉树中一种"排得整整齐齐"的结构，它的定义是：

完全二叉树的定义

1. 除最后一层外，每一层都被完全填满（节点数达到最大值）。

2. 最后一层的节点从左到右排列，中间不能有空位。

简单说：就像一个队列，从上到下、从左到右依次填满，最后一层可以没填完，但不能"跳着"填。

动手判断：下面哪些是完全二叉树？

点击每张卡片，看看对不对。注意最后一层节点的排列方式。

记忆口诀

"层满左对齐" —— 除最后一层全满，最后一层从左到右不留空。这就是完全二叉树。

完全二叉树 vs 满二叉树

别搞混！

满二叉树（Perfect Binary Tree）：每个非叶子节点都有两个子节点，所有叶子在同一层。它是完全二叉树的特例。

完全二叉树（Complete Binary Tree）：允许最后一层不满，但必须从左到右排满。范围更宽。

所以：满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树。

第二课

递归判定思路

怎么用一次 DFS 判断所有子树？秘诀是：对每个节点维护三个属性，后序遍历时自底向上算出来。

每个节点要算什么？

height[u]

子树的高度（最深叶子到 u 的距离）。叶子高度 = 0。

isPerfect[u]

子树是否是满二叉树（所有层都填满）。

isComplete[u]

子树是否是完全二叉树。这是我们最终要的答案。

递归规则表

根据节点 u 的子节点情况，分四种情形：

情形	height	isPerfect	isComplete
叶子（无子）	0	true	true
只有左子 l	h[l]+1	false	h[l]==0（左子是叶子）
只有右子 r	h[r]+1	false	false
有左右子 l, r	max(h[l],h[r])+1	perf[l] && perf[r] && h[l]==h[r]	见下方

有左右子时，isComplete 的判定

设 hL = h[l]，hR = h[r]：

1. hL == hR（左右等高）：左子树必须满，右子树可以"缺"最后一层。
isComplete = isPerfect[l] && isComplete[r]

2. hL == hR + 1（左比右高一层）：左子树可以"缺"最后一层，右子树必须满。
isComplete = isComplete[l] && isPerfect[r]

3. 其他（高度差过大）：isComplete = false

为什么等高时左子树必须"满"？

想象从上到下、从左到右给节点编号。当左右子树等高时，最后一层横跨两棵子树。如果左子树有"缺口"（不满），而右子树还有节点，就违反了"从左到右排满"——左边的位置空着，右边却有节点。所以等高时左子树必须满（isPerfect），右子树可以缺（isComplete）。

而左比右高一层时，最后一层只在左子树里，右子树是倒数第二层——必须满。左子树可以缺（isComplete），右子树必须满（isPerfect）。

互动：点击节点查看属性

用样例 2 的树（有一棵子树不是完全二叉树）。点击任意节点，右侧面板会显示它的高度、isPerfect、isComplete。

节点属性

点击树上的节点

图例

完全二叉树

非完全二叉树

满二叉树

未判定

第四课

C++ 代码

核心就是一个后序 DFS，对每个节点算三个属性，最后数 isComplete 为 true 的节点。

C++ · GESP 六级

// 完全二叉子树计数 - O(n) 后序 DFS
#include <iostream>
using namespace std;

const int N = 100005;
int n, lc[N], rc[N];
int h[N];           // 子树高度
bool perf[N], comp[N];  // isPerfect, isComplete

void dfs(int u) {
    int l = lc[u], r = rc[u];
    if (l == 0 && r == 0) {
        // 叶子节点
        h[u] = 0;
        perf[u] = true;
        comp[u] = true;
    } else if (l != 0 && r == 0) {
        // 只有左子
        dfs(l);
        h[u] = h[l] + 1;
        perf[u] = false;
        comp[u] = (h[l] == 0);  // 左子必须是叶子
    } else if (l == 0 && r != 0) {
        // 只有右子 → 不可能完全
        dfs(r);
        h[u] = h[r] + 1;
        perf[u] = false;
        comp[u] = false;
    } else {
        // 有左右子
        dfs(l);
        dfs(r);
        h[u] = max(h[l], h[r]) + 1;
        perf[u] = perf[l] && perf[r] && (h[l] == h[r]);
        if (h[l] == h[r]) {
            comp[u] = perf[l] && comp[r];
        } else if (h[l] == h[r] + 1) {
            comp[u] = comp[l] && perf[r];
        } else {
            comp[u] = false;
        }
    }
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> lc[i] >> rc[i];
    dfs(1);
    int cnt = 0;
    for (int i = 1; i <= n; i++)
        if (comp[i]) cnt++;
    cout << cnt << endl;
    return 0;
}

复杂度分析

时间复杂度：O(n) —— 每个节点只访问一次。

空间复杂度：O(n) —— 数组 + 递归栈。对于 n = 10⁵，最坏情况（退化为链）递归深度可达 10⁵，可能在某些评测机上爆栈。如果遇到这个问题，可以改成迭代式后序遍历。

第五课

互动练习

这是一棵更大的树（9 个节点）。点击任意节点，查看它的子树属性。点击"显示所有结果"可以一键看到哪些子树是完全二叉树。