🌲 完全二叉树子树计数 · 精讲

0先翻译题目

题干给了我们一棵「有根二叉树」：1 号是根，每个点 i 有左儿子 li 和右儿子 ri（0 表示没有）。

所以这题有两步：① 搞清楚什么叫「完全二叉树」；② 设计一个能同时判断 n 棵子树的高效方法。n 最大 10⁵，不能一棵一棵去扫（那就 O(n²) 了），必须一次遍历把 n 个答案全算出来——这就是「树 DP（动态规划）」的思想。

1什么是完全二叉树？

完全二叉树 = 一层一层从左往右填，除了最后一层，其它层必须填满；最后一层也必须从左到右连续，不能有「空位」。

注意区分三个容易混的词：

• 满二叉树（也叫完美二叉树）：每一层都完全填满 → 节点数 = 2^高度−1。
• 完全二叉树：只要求「除了最后一层都满，最后一层靠左连续」。满二叉树一定是完全二叉树，反过来不一定。
• 普通二叉树：随便怎么长都行。

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

2三个判定量：h、满、完全

要判断「子树是不是完全二叉树」，只需要给每个节点存三个信息：

关键：这三个量都只和「孩子」有关——先算孩子，就能算爸爸。这就是「自底向上」的树 DP。

🖱️ 判案练习：点击树上的节点，看它「管着」的子树是不是完全二叉树

这棵演示树有 10 个点。点一下任意节点，它的整棵子树会亮起来，同时给出判决和理由！

3判定规则：四种情况

节点 u 的子树是否完全，看它的孩子情况（hl = 左子树高度，hr = 右子树高度）：

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

程序用后序遍历（先左、后右、再自己）把树走一遍：孩子算完才轮到爸爸，正好符合「自底向上」。每处理一个节点就填好它的 h / 满 / 完全，如果是完全二叉树就计数 +1。绿色 = 完全，红色 = 不完全。

后序遍历的顺序是 4, 5, 2, 8, 6, 9, 10, 7, 3, 1——每个节点算的时候，它的孩子一定已经算完了。数一数绿色：2、4、5、6、7、8、9、10 共 8 棵。

5C++ 代码

n 最大 10⁵，树可能长成一条「斜链」——递归会爆栈，所以主代码用迭代后序遍历（显式栈）。三个数组 h / full / ok 就是上一节动画里填的表。

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

const int N = 100005;
int lc[N], rc[N];      // 左儿子、右儿子（0 = 没有）
int h[N];              // 子树高度（叶子 = 1）
bool full[N];          // 是不是满二叉树
bool ok[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; ok[u] = true;
        }
        else if (l && r) {                          // 情况④ 两个孩子
            int hl = h[l], hr = h[r];
            h[u] = (hl > hr ? hl : hr) + 1;
            full[u] = full[l] && full[r] && (hl == hr);
            ok[u] = false;
            if (ok[l] && ok[r]) {
                if (hl == hr) ok[u] = full[l];       // 等高 → 左边要满
                else if (hl == hr + 1) ok[u] = full[r]; // 左高1 → 右边要满
            }
        }
        else if (l) {                                // 情况② 只有左孩子
            h[u] = h[l] + 1; full[u] = false;
            ok[u] = (h[l] == 1);                     // 左孩子必须是叶子
        }
        else {                                       // 情况③ 只有右孩子
            h[u] = h[r] + 1; full[u] = false; ok[u] = false;
        }
        if (ok[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; ok[u] = true; }
    else if (l && r) {
        h[u] = max(h[l], h[r]) + 1;
        full[u] = full[l] && full[r] && h[l] == h[r];
        ok[u] = ok[l] && ok[r] &&
                ((h[l] == h[r] ? full[l] : (h[l] == h[r] + 1 ? full[r] : false)));
    }
    else if (l) { h[u] = h[l] + 1; full[u] = false; ok[u] = (h[l] == 1); }
    else        { h[u] = h[r] + 1; full[u] = false; ok[u] = false; }
}

6小测验

7总结 & 考点