完全二叉树?

完全二叉树?

时间: 1ms        内存:128M

描述:

二叉树T中,如果非叶子结点都有两棵非空子树,那么称二叉树T是一棵完全二叉树。现在根据边的连接情况判断一棵树是否是完全二叉树。

输入:

第一行有2个整数n(0 < n < 1024)和r(1<=r<=n), 表示结点数和树根,接下来n-1行每行有2个整数a,b (1 <= a,b <= n)表示a结点和b结点有一条边相连(数据保证是一棵树而不是一座森林)

输出:

如果是完全二叉树 输出yes 否则输出no

示例输入:

5 1
1 2
3 1
4 2
2 5 

示例输出:

yes

提示:

参考答案(内存最优[748]):

#include<stdio.h>    
#include<stdlib.h>  
#include<string.h> 
int main() 
{    
    int bitree[1025],n,r,i,a,b;    
    memset(bitree,0,sizeof(bitree));    
    scanf("%d %d",&n,&r);    
    if(n%2 == 0) 
	{    
           printf("no\n");    
           return 0;    
    }    
    bitree[r] = 1;    
    for(i = 1;i <= n-1;i++) 
	{    
          scanf("%d %d",&a,&b);    
          bitree[a]++;    
          bitree[b]++;    
    }    
    for(i = 1;i <= n;i++) 
	{    
          if(bitree[i] != 3 && bitree[i] != 1) 
		  {    
             printf("no\n");    
             return 0;    
          }    
    }       
    printf("yes\n");  
	return 0;
}   


参考答案(时间最优[0]):

#include<stdio.h>    
#include<stdlib.h>  
#include<string.h> 
int main() 
{    
    int bitree[1025],n,r,i,a,b;    
    memset(bitree,0,sizeof(bitree));    
    scanf("%d %d",&n,&r);    
    if(n%2 == 0) 
	{    
           printf("no\n");    
           return 0;    
    }    
    bitree[r] = 1;    
    for(i = 1;i <= n-1;i++) 
	{    
          scanf("%d %d",&a,&b);    
          bitree[a]++;    
          bitree[b]++;    
    }    
    for(i = 1;i <= n;i++) 
	{    
          if(bitree[i] != 3 && bitree[i] != 1) 
		  {    
             printf("no\n");    
             return 0;    
          }    
    }       
    printf("yes\n");  
	return 0;
}   


题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注