数据结构与算法分析笔记与总结(java实现)--二叉树6:完全二叉树判断练习题

时间:2021-08-16 09:51:30

题目:有一棵二叉树,请设计一个算法判断它是否是完全二叉树。给定二叉树的根结点root,请返回一个bool值代表它是否为完全二叉树。树的结点个数小于等于500。

思路:判断一棵树是否是完全二叉树,显然按照完全二叉树的定义应该使用按层遍历的方式来进行。按层遍历使用while循环并借助队列来进行。逐个元素遍历:每弹出一个结点temp要将其左右结点放入到队列中,逻辑:如果temp既有左孩子又有右孩子,那么继续向下进行;如果temp只有有孩子没有左孩子那么显然不是完全二叉树,返回false,结束方法;如果temp只有左孩子没有右孩子或者没有任何孩子,那么制定一个标记flag=1,之后如果某个结点有任何孩子都不是完全二叉树;当遍历完全部的结点后如果依然没有返回那么就是完全二叉树,返回true。

注意:在面试中,通常二叉树中任何结点都只有一个值val和left、right子节点,没有指向父节点的指针,但在工程上通常有指向父节点的指针。

即判断是否是完全二叉树其实很简单,只有四种情况,分别做判断即可:

情况1:temp的left!=null&&right!=null,那么不做处理,继续遍历

情况2:temp的left==null&&right!=null,那么显然不是完全二叉树,return false;

情况3:temp的left!=null&&right==null,那么对之后遍历的结点需要特殊考察,如果之后的结点还有子节点就不是完全二叉树,返回false,这里使用一个标记遍历flag来作为循环时是否允许子节点为空的依据。

情况4:temp的left==null&&right==null,那么同上,对之后遍历的结点要特殊考察。只是情况3中要将结点left放入队列中,情况4中不需要将结点放入队列中。

importjava.util.*;

//判断是否是完全二叉树:按层遍历,借助队列来实现

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;

    }

}