🌲 满二叉树子树计数 · 图文动画精讲（GESP 六级）

0先翻译题目

和上一题结构一模一样：一棵有根二叉树（1 号是根，每个点 i 有左儿子 l_i 和右儿子 r_i，0 = 没有），数一数 n 棵子树里有几棵是「满二叉树」。

题目里满二叉树的定义：① 所有叶子深度都相同；② 除叶子外，每个节点都有两个儿子。
换句话说：每一层都被填满的二叉树（也叫「完美二叉树」）。

🔗 和上一题「完全二叉树」的区别（最容易混！）：
完全二叉树：只要求「最后一层从左到右连续」，允许最后一层不满。
满二叉树：每一层都必须填满，最严格。
所以：满 ⇒ 完全（满的树一定是完全的），但反过来不一定。
例子：只有左孩子的两个点 → 完全 ✓ 但满 ✗。这就是两题答案会不一样的原因。

1什么是满二叉树？

满二叉树 = 每一层都填满。如果它的高度是 h，那节点数一定是 2^h − 1（1、3、7、15……个节点）。

满（每层都填满）✓

只有左孩子：完全 ✓ 但满 ✗

有缺口：完全 ✗ 满 ✗

⚠️ 记牢：满二叉树三个等价说法——① 所有叶子深度相同；② 每个非叶子都有两个孩子；③ 节点数 = 2^高度 − 1。判定代码里我们直接用③的等价形式：左右子树都满且高度相等。

🔍 判定小测试：这些子树是满二叉树吗？（点选项看对错）

① 只有 1 个节点（叶子）

✔️ 是！题目说叶子也算满二叉树（所有叶子深度相同，就它自己）。

② 根 + 两个叶子（3 个点）

✔️ 是！高度 2，节点数 3 = 2²−1，每层都填满。

③ 根 + 只有左孩子（2 个点）

✔️ 不是！根是非叶子节点，但它只有 1 个孩子 → 违反「非叶子必须有两个儿子」。注意：它其实是完全二叉树哦！

④ 7 个点，三层全满

✔️ 是！高度 3，节点数 7 = 2³−1，每层都满。

⑤ 1(2,3)，3(4,5)（5 个点，题面例子）

✔️ 不是！叶子 2 在深度 2，叶子 4、5 在深度 3 —— 叶子深度不同 → ✗（虽然每个非叶子都有两个孩子）。

⑥ 1(2,3)，2(4,0)，3(5,0)（5 个点）

✔️ 不是！左右子树高度都是 2，但 2、3 各自都只有左孩子（不满）→ 高度相等也不满 → ✗。「等高」≠「满」！

🎯 一句话记法：满二叉树 = 节点数 = 2^高度−1 = 左右都满且等高。三个说法，见到哪个都能认。

2判定规则：只需要两个量

和上一题比，这题的判定简单得多——只需要记两个信息，连「完全」那个麻烦规则都不用：

信息	含义	怎么算
高度 h	子树有多高（叶子 = 1）	max(左高, 右高) + 1
满 full	是不是满二叉树 ← 我们要的答案	见下面三种情况

情况 ① 叶子（没有孩子） → 是满二叉树 ✓

高度 1，只有一个节点，所有叶子深度相同（都是 1）。

情况 ② 两个孩子都有 → 左子树满 && 右子树满 && 左右等高 → 才满 ✓

满 = 每一层都填满。左右等高，左右又都满 → 整棵树每层都满。
缺一个都不行：等高但有一边不满 ✗；两边都满但不等高 ✗（叶子深度不同）。

情况 ③ 只有一个孩子 → 永远不是满二叉树 ✗

自己是非叶子节点，却只有一个孩子 → 违反「非叶子必须有两个儿子」，直接 ✗。

💡 和上一题对比：完全二叉树要记 3 个量（高度、满、完全），判定规则还有「等高要左边满 / 左高 1 要右边满」的不对称细节；满二叉树只要记 2 个量，规则对称简洁——两个孩子都满且等高就完事。这就是出题人把两题放一起考的原因：一个考复杂规则的细心，一个考基础的扎实。

3🖱️ 判案练习：点击节点，看它的子树是不是满二叉树

这棵演示树和上一题是同一棵（10 个点）。上一题数完全二叉树答案是 8，这题数满二叉树答案会变成 7——到底差在哪？点节点 6 看看！

是满二叉树不是满二叉树选中的节点

👆 点一个节点，我来判案！

🔍 谜底：节点 6 的子树只有「6 和它的左孩子 8」——它是完全二叉树（上一题 ✓），但 6 只有一个孩子，不是满二叉树（这题 ✗）。这就是两题答案差 1 的地方：完全 8 棵 vs 满 7 棵。

4动画：后序遍历 DP 全过程

程序用后序遍历（先左、后右、再自己）自底向上算：孩子先算完，爸爸就能直接填 h 和 full。每处理一个节点，是满就计数 +1。绿色 = 满，红色 = 不满。

还没访问在栈中(孩子还没处理完) 处理完：满 ✓ 处理完：不满 ✗ 当前处理

栈：空

DP 表：（还没处理任何节点）

后序遍历顺序 4, 5, 2, 8, 6, 9, 10, 7, 3, 1。绿色节点：2、4、5、7、8、9、10 共 7 棵；节点 6 和 3 以及根 1 都是红色。

5C++ 代码

和上一题同款套路：迭代后序遍历（防止 10⁵ 斜链爆栈）+ 自底向上填 h 和 full。判定规则比上一题短一截——没有「完全」那个不对称的麻烦。

#include <iostream>
#include <stack>
using namespace std;

const int N = 100005;
int lc[N], rc[N];      // 左儿子、右儿子（0 = 没有）
int h[N];              // 子树高度（叶子 = 1）
bool full[N];          // 是不是满二叉树 ← 答案

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> lc[i] >> rc[i];

    // 迭代后序遍历：先左、后右、再自己
    int order[N];                       // 存后序顺序
    int cntOrder = 0;
    stack<pair<int,int>> st;           // <节点, 0=先去孩子 1=孩子处理完>
    st.push(make_pair(1, 0));
    while (!st.empty()) {
        int u = st.top().first, s = st.top().second;
        st.pop();
        if (s == 0) {
            st.push(make_pair(u, 1));
            if (rc[u]) st.push(make_pair(rc[u], 0));
            if (lc[u]) st.push(make_pair(lc[u], 0));
        } else {
            order[cntOrder++] = u;
        }
    }

    // 自底向上 DP
    int ans = 0;
    for (int k = 0; k < cntOrder; k++) {
        int u = order[k];
        int l = lc[u], r = rc[u];
        if (l == 0 && r == 0) {         // 情况① 叶子
            h[u] = 1; full[u] = true;
        }
        else if (l && r) {               // 情况② 两个孩子
            h[u] = (h[l] > h[r] ? h[l] : h[r]) + 1;
            full[u] = full[l] && full[r] && (h[l] == h[r]);  // 都满且等高
        }
        else {                           // 情况③ 只有一个孩子
            h[u] = (l ? h[l] : h[r]) + 1;
            full[u] = false;
        }
        if (full[u]) ans++;
    }

    cout << ans << endl;
    return 0;
}

时间复杂度 O(n)，空间 O(n)。

📖 递归版（代码更短，但斜链大数可能爆栈，慎用）

void dfs(int u) {
    if (u == 0) return;
    dfs(lc[u]); dfs(rc[u]);            // 先孩子
    int l = lc[u], r = rc[u];
    if (l == 0 && r == 0) { h[u] = 1; full[u] = true; }
    else if (l && r) {
        h[u] = max(h[l], h[r]) + 1;
        full[u] = full[l] && full[r] && h[l] == h[r];
    } else {
        h[u] = (l ? h[l] : h[r]) + 1;
        full[u] = false;
    }
    if (full[u]) ans++;
}

6小测验

1️⃣ 满二叉树的定义是？（题目原话）

✔️ 所有叶子深度相同 + 非叶子都有两个儿子 = 每层都填满。第二项是「完全二叉树」，第三项是普通二叉树。

2️⃣ 单个叶子节点，是满二叉树吗？

✔️ 是！题目明说了叶子也算（所有叶子深度相同，就它自己）。而且样例 1 的答案 2 就包含了两个叶子。

3️⃣ 一个节点只有左孩子（右孩子），它的子树是满二叉树吗？

✔️ 不是！非叶子节点必须有两个孩子。注意：这种子树是「完全」但不是「满」——两题的区别就在这。

4️⃣ 两个孩子都有，要成为满二叉树，必须满足？

✔️ 左右都满且等高，缺一不可！等高但有一边不满 = 那层没填满；都满但不等高 = 叶子深度不同。

5️⃣ 满二叉树的子树，一定是完全二叉树吗？（联系上一题）

✔️ 一定是！满 = 每层都填满，自然满足「除最后一层全满 + 最后一层连续」。反过来不行：只有左孩子 → 完全但不满。

6️⃣ n = 10⁵ 时，这题怎么做？

✔️ 一次后序遍历！每个节点只算一次，O(n)。

7总结 & 两题对比

对比	完全二叉树（上一题）	满二叉树（这题）
定义	除最后一层全满 + 最后一层从左到右连续	每一层都填满（叶子同深度 + 非叶子都有两个孩子）
例子：只有左孩子	✓ 是	✗ 不是
DP 要记几个量	3 个：高度 + 满 + 完全	2 个：高度 + 满
两个孩子的规则	等高→左边满；左高1→右边满（不对称，易错）	左右都满且等高（对称，好记）
同一棵演示树	8 棵	7 棵（差节点 6：完全但不满）

🎯 树 DP 套路小结（两题通用）：① 想清楚每个节点要维护哪几个量；② 用后序遍历保证「孩子先算完」；③ 自底向上填表；④ n 大用迭代栈防爆栈。这套路会陪你到七级。

下一题可以挑战：二叉树的后序遍历序列还原、求树的高度/直径，或者回来把两题（完全 + 满）一起刷一遍对比手感。想学哪个，跟我说！