G6024 [GESP202606 六级] 满二叉树 题解

知识点：树形动态规划、完美二叉树、后序遍历。

解题思路

后序维护高度，若左右子树都有效且高度相同，则当前子树满，高度加1并计数；否则标为-1。

为什么正确

满二叉树必须每层填满，等价于左右都是满树且同高；由空树起归纳可正确判断所有子树。

易错点

本题的“满”指每层节点完整的完美二叉树，不只是每个节点度数为0或2。

复杂度

时间O(n)，空间O(n)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<array<int,2>>ch(n+1);
    for(int i=1;i<=n;i++)cin>>ch[i][0]>>ch[i][1];
    vector<int>q= {
        1
    }
    ;
    for(int k=0;k<(int)q.size();k++)for(int v:ch[q[k]])if(v)q.push_back(v);
    vector<int>h(n+1);
    int ans=0;
    reverse(q.begin(),q.end());
    for(int u:q) {
        int l=ch[u][0],r=ch[u][1];
        if(h[l]>=0&&h[r]>=0&&h[l]==h[r]) {
            h[u]=h[l]+1;
            ans++;
        }
        else h[u]=-1;
    }
    cout<<ans;
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用12个自行生成的测试点。