1110 Complete Binary Tree (25 分)【难度: 一般 / 知识点: 判断完全二叉树】

1110 Complete Binary Tree (25 分)【难度: 一般 / 知识点: 判断完全二叉树】
https://pintia.cn/problem-sets/994805342720868352/problems/994805359372255232
1110 Complete Binary Tree (25 分)【难度: 一般 / 知识点: 判断完全二叉树】
建树并给其赋值,如果是完全二叉树,那么maxid一定为n,否则则不是完全二叉树。
找根节点,就找到入度为0的点就是根节点。

#include<bits/stdc++.h>
using namespace std;
int l[30],r[30];
int n,root,last,maxid,d[25];
void dfs(int u,int k)
{
    if(maxid<k)
    {
        maxid=k,last=u;
    }
    if(l[u]!=-1) dfs(l[u],k*2);
    if(r[u]!=-1) dfs(r[u],k*2+1);
}
int main(void)
{
    memset(l,-1,sizeof l);
    memset(r,-1,sizeof r);
    cin>>n;
    for(int i=0;i<n;i++)
    {
        string a,b; cin>>a>>b;
        if(a!="-") l[i]=stoi(a),d[stoi(a)]++;
        if(b!="-") r[i]=stoi(b),d[stoi(b)]++;
    }
    for(int i=0;i<n;i++) if(d[i]==0) root=i;
    dfs(root,1);
    if(maxid==n) printf("YES %d",last);
    else printf("NO %d",root);
    return 0;
}
上一篇:C/C++ atol函数- C语言零基础入门教程


下一篇:PAT(乙级)2020年秋季考试(模拟赛)