判断一棵树是不是满二叉树
作者:
无敌大废物
,
2023-11-13 19:02:21
,
所有人可见
,
阅读 106
//如果一棵树是满的,则2^高度-1=节点数
public class d2 {
//暴力
public static int getheight(node root){
if(root==null){
return 0;
}
int l=getheight(root.left);
int r=getheight(root.right);
return Math.max(l,r)+1;
}
public static int getnodenum(node root){
if(root==null){
return 0;
}
int lnum=getnodenum(root.left);
int rnum=getnodenum(root.right);
return lnum+rnum+1;
}
public static boolean isfull1(node root){
if(root==null){
return true;
}
int height=getheight(root);
int nodenum=getnodenum(root);
if(2<<height-1==nodenum){
return true;
}
return false;
}
//dp
public static class info{
boolean f;
int height;
int nodenum;
public info(boolean a,int b,int c){
f=a;height=b;nodenum=c;
}
}
public static boolean isfull2(node root){
if(root==null){
return true;
}
return getinfo(root).f;
}
public static info getinfo(node root){//获取信息
if(root==null){
return new info(true,0,0);
}
info l=getinfo(root.left);
info r=getinfo(root.right);
int height=Math.max(l.height,r.height)+1;
int num=l.nodenum+r.nodenum+1;
boolean f=true;
if(2<<height-1!=num){
f=false;
}
return new info(f,height,num);
}
}