首页 > 代码库 > PAT甲题题解-1110. Complete Binary Tree (25)-(判断是否为完全二叉树)

PAT甲题题解-1110. Complete Binary Tree (25)-(判断是否为完全二叉树)

题意:判断一个节点为n的二叉树是否为完全二叉树。Yes输出完全二叉树的最后一个节点,No输出根节点。

建树,然后分别将该树与节点树为n的二叉树相比较,统计对应的节点个数,如果为n,则为完全二叉树,否则即不是。

技术分享
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string.h>

using namespace std;
const int maxn=22;
int two[6];
int lastNode;
struct Node{
    int left,right;
    int id;
}tree[maxn],cbt[maxn];

/*
将输入给的二叉树和节点为n的完全二叉树一个个作比较,计算对应的节点个数
如果节点个数为n,则二叉树为完全二叉树。
i为完全二叉树的当前节点编号。
root为输入二叉树的对应节点。
*/
int compare(int root,int i,int n){
    int res1=-1,res2=-1;
    if(root==-1){
        return 0;
    }
    if(i==n)
        lastNode=root; //记录完全二叉树的最后一个节点的id
    int sum=0;

    if(2*i<=n){
        sum+=compare(tree[root].left,i*2,n);
    }
    if(2*i+1<=n){
        sum+=compare(tree[root].right,i*2+1,n);
    }
    bool flag1=false,flag2=false;
    if((2*i<=n&&tree[root].left!=-1)||(2*i>n&&tree[root].left==-1))
        flag1=true;
    if((2*i+1<=n&&tree[root].right!=-1)||(2*i+1>n&&tree[root].right==-1))
        flag2=true;
    if(flag1 && flag2)
        sum++;
    return sum;
}
int main()
{
    int n;
    scanf("%d",&n);
    char str1[10],str2[10];
    int a;
    int vis[maxn];
    memset(vis,-1,sizeof(vis));
    for(int i=0;i<n;i++){
        scanf("%s %s",str1,str2);
        tree[i].id=i;
        if(str1[0]==-)
            tree[i].left=-1;
        else{
            a=atoi(str1);
            tree[i].left=a;
            vis[a]=1;
        }
        if(str2[0]==-)
            tree[i].right=-1;
        else{
            a=atoi(str2);
            tree[i].right=a;
            vis[a]=1;
        }
    }
    int root;
    for(int i=0;i<n;i++){
        if(vis[i]==-1)
            root=i;
    }

    if(compare(root,1,n)==n){
        printf("YES %d",lastNode);
    }
    else{
        printf("NO %d",root);
    }
    return 0;
}
View Code

 

该博客里的解题方法要比我好一点,即按照层次遍历该二叉树,每遍历一个节点cnt++,直到为-1。此时cnt=n,则Yes,否则No。

http://www.liuchuo.net/archives/2158

PAT甲题题解-1110. Complete Binary Tree (25)-(判断是否为完全二叉树)