G6022 [GESP202603 六级] 完全二叉树 题解

知识点：树形动态规划、完全二叉树、状态合并。

解题思路

后序计算每棵子树高度、是否满层和是否完全。完全二叉树除满层外，只有“左完全右满且左高1”或“左满右完全且等高”两种结构，统计成立节点。

为什么正确

完全二叉树的最后一层只能从左向右填充，这恰限制为上述两个结构；结合子树归纳可判定每个根的整棵子树。

易错点

空树高度0并视为满且完全；不能只比较左右高度，必须检查左右状态。

复杂度

时间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),full(n+1,1),complete(n+1,1);
    int ans=0;
    reverse(q.begin(),q.end());
    for(int u:q) {
        int l=ch[u][0],r=ch[u][1];
        h[u]=max(h[l],h[r])+1;
        full[u]=full[l]&&full[r]&&h[l]==h[r];
        complete[u]=full[u]||(complete[l]&&full[r]&&h[l]==h[r]+1)||(full[l]&&complete[r]&&h[l]==h[r]);
        ans+=complete[u];
    }
    cout<<ans;
}

说明

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