【GESP202603六级】完全二叉树

此题中核心思路是使用DFS(深度优先搜索),再加上以下2句话:
1:当x的左子树为满二叉树，右子树为完全二叉树，且x的左孩子高度与右孩子则高度相等,则x一定为完全二叉树
2:当x的左孩子高度等于右孩子高度加一，且左子树为完全二叉树，右子树为满二叉树，则x一定是完全二叉树

知道了思路，就要实现，我们要数组 n:有n个结点 ans:有多少个完全二叉树 l数组:第i号节点的左孩子 r数组:第i号节点的右孩子 c数组:(可使用bool类型)已i节点为根的二叉树是否是完全二叉树 f数组(可使用bool类型):i的子树是否为满二叉树 h数组:第i个节点的高度(深度)(注意:根节点高度(深度)为一)

接下来是代码了:

//重在理解，不是抄
#include<bits/stdc++.h>
using namespace std;
int n,l[100010],r[100010],h[100010],ans,c[100010],f[100010];
//n:有n个结点    ans:有多少个完全二叉树    l数组:第i号节点的左孩子
//r数组:第i号节点的右孩子    c数组(可使用bool类型):已i节点为根的二叉树是否是完全二叉树
//f数组(可使用bool类型):i的子树是否为满二叉树    
//h数组:第i个节点的高度(深度)
void dfs(int x){
    //x:当前节点
    if(x==0){
        //判断x是否为叶子结点
        h[x]=0;
        c[x]=1;
        f[x]=1;
        return ;
    }
    //遍历x的左孩子
    dfs(l[x]);
    //遍历x的右孩子
    dfs(r[x]);
    //x结点当前高度，为左孩子与右孩子的最大值加一
    h[x]=max(h[l[x]],h[r[x]])+1;
    //判断x节点是否为满二叉树，f数组存储
    f[x]=(f[l[x]]&&f[r[x]]&&h[l[x]]==h[r[x]]);
    //先认定x不是完全二叉树
    c[x]=0;
    //当x的左子树为满二叉树，右子树为完全二叉树，且x的左孩子高度与右孩子
    //高度相等,则x一定为完全二叉树
    if(f[l[x]]&&c[r[x]]&&h[l[x]]==h[r[x]]) c[x]=1;
    //当x的左孩子高度等于右孩子高度加一，且左子树为完全二叉树，右子树为满二叉树
    //则x一定是完全二叉树
    if(c[l[x]]&&f[r[x]]&&h[l[x]]==h[r[x]]+1) c[x]=1;
    //判断x是否为完全二叉树，如果是完全二叉树数量加一
    if(c[x]) ans++;
}
int main(){
    //基本输入
    //*---------------*
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>l[i]>>r[i];
    }
    //*---------------*
    //进入递归
    dfs(1);
    //输出答案
    cout<<ans;
}