首页 > 代码库 > 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; }
该博客里的解题方法要比我好一点,即按照层次遍历该二叉树,每遍历一个节点cnt++,直到为-1。此时cnt=n,则Yes,否则No。
http://www.liuchuo.net/archives/2158
PAT甲题题解-1110. Complete Binary Tree (25)-(判断是否为完全二叉树)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。