判断二叉树是否为完全二叉树的实例
完全二叉树特点
完全二叉树是指除了最后一层之外,其他每一层的结点数都是满的。最后一层如果也满了,是一颗满二叉树,也是完全二叉树。最后一层如果不满,缺少的结点也全部的集中在左边,那也是一颗完全二叉树。
判断一棵二叉树是否为完全二叉树
importjava.util.*; classTreeNode{ intval=0; TreeNodeleft=null; TreeNoderight=null; publicTreeNode(intval){ this.val=val; } } publicclassCheckCompletion{ publicbooleanchecking(TreeNoderoot){ Queuequeue=newLinkedList (); booleanleaf=false;//叶子结点 TreeNodeleft; TreeNoderight; queue.add(root); while(!queue.isEmpty()){ root=queue.poll(); left=root.left; right=root.right; if((leaf&&(left!=null||right!=null))||(left==null&&right!=null)){ //如果之前层遍历的结点没有右孩子,且当前的结点有左或右孩子,直接返回false //如果当前结点有右孩子却没有左孩子,直接返回false returnfalse; } if(left!=null){ queue.offer(root.left); } if(right!=null){ queue.offer(root.right); }else{ leaf=false;//如果当前结点没有右孩子,那么之后层遍历到的结点必须为叶子结点 } } returntrue; } }
感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!