判断一棵树是否是完全二叉树
程序员文章站
2022-05-16 10:35:50
...
二叉树:
1.满二叉树:在一棵二叉树中,如果所有分支节点都存在左子树和右子树,并且所有叶子节点都在同一层上。
2.完全二叉树:如果一棵具有N个结点的二叉树的结构与满二叉树的前N个结点的结构相同,称为完全二叉树。
//判断是否是完全二叉树:按层遍历,借助队列来实现
publicclass CheckCompletion {
public boolean chk(TreeNode root) {
//①创建一个队列
LinkedList<TreeNode> queue=newLinkedList<>();
//②将根结点放入队列
TreeNode temp=root;
queue.add(temp);
//③循环:弹出--压入左右子节点
boolean flag=true;
while(queue.size()!=0){
temp=queue.poll();
TreeNode left=temp.left;
TreeNode right=temp.right;
//如果flag==false说明之前的结点只有左结点或者没有子节点,因此之后的结点都不能有子节点
if((!flag)&&(left!=null||right!=null)) return false;
if(left!=null&&right!=null){
//左右结点都存在
queue.add(left);
queue.add(right);
}elseif(left==null&&right!=null){
//右结点存在,左结点不存在,一定为false
return false;
}elseif(left!=null&&right==null){
//左结点存在右结点不存在则接着遍历,只是之后的结点都不能有孩子,作一个标记记录
flag=false;
//当然存在的子节点还是要放入到队列中
queue.add(left);
}else{
//左右结点都为空,则不需要放入队列,只要做标记,之后的结点都不能有子节点
flag=false;
}
}
//当队列为空时,说明遍历完成,此时还没有返回说明是完全二叉树
return true;
}
}
上一篇: 判断一棵树是否是二叉搜索树