欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

判断一棵树是否是完全二叉树

程序员文章站 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;
    }
}