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

旧城等待， 2022-05-16 13:52 231阅读 0赞

判断一棵二叉树是否为完全二叉树–采用广度优先遍历–利用队列  
\* 1。定义标志位flag=false表示没有遇到空的节点，count=0  
\* 2.只要树中节点的左右子树都不为空，那么就把该节点的所有左右孩子压入队列（包括null节点）  
\* 压入队列3种情况：  
\* （1）节点都有左右子节点—都压入  
\* （2）节点有一个左子节点右子节点为空或者节点有一个右子节点左子节点为空—把不为空的子节点和为空的子节点都压入  
\* （3）节点左右子节点都为空，那么不压入该节点的左右子节点  
\* 3.对于每个出队的节点都判断以下该节点是否为空，如果为空，则flag=true，count=1，  
\* 如果出队节点不为空，在判断count是否为1，如果是，说明该节点以前已经遇到了空节点，把flag置为false，直接返回结果，没有必要再继续向后遍历了。  
\* 如果count！=1，此时count=0，说明二叉树为满二叉树，此时把flag置为true。对于完全二叉树来说，除最后一层外节点都是满的，  
\* 只有最后一层叶子节点都是从左到右依次排序的，即节点都在左侧。如果一个节点为空，在向后遍历时发现有非空节点存在那么该树一定不是完全二叉树  
\* 4.直接返回flag即可或者判断flag  
\* if(flag==true)  
\* return true;  
\* else  
\* return false;

public class isCompleteTree {
        public static boolean isCompleteBinaryTree(TreeNode root){
            if(root==null||(root.left==null&&root.right==null))
                return true;//空树或者只有一个根节点的树也是完全二叉树
            Queue<TreeNode> q=new LinkedList<>();
            q.offer(root);
            boolean flag=false;
            int count=0;
            while(!q.isEmpty()){
                TreeNode cur=q.poll();
                if(cur!=null&&(cur.left!=null||cur.right!=null)){
                    q.offer(cur.left);
                    q.offer(cur.right);
                }
                if(cur==null){
                    flag=true;
                    count=1;//或者count++； 
                }
                else{
                    if(count==1){
                        flag=false;
                        return flag;//如果count=1直接返回结果，退出循环，已经遇到空的节点，没有必要再继续循环遍历下去了
                    }
                    else
                        flag=true;
                }           
            }
    // if(flag==true)
    // return true;
    // else
    // return false;
            return flag;
    
        }
        public static void main(String[] args) {
            TreeNode root1=new TreeNode(1);
            TreeNode root2=new TreeNode(2);
            TreeNode root3=new TreeNode(3);
            TreeNode root4=new TreeNode(4);
            TreeNode root5=new TreeNode(5);
            TreeNode root6=new TreeNode(6);
            //TreeNode root7=new TreeNode(7);
            root1.left=root2;
            root1.right=root3;
            root2.left=root4;
            root2.right=root5;
            root3.left=root6;
            //root3.right=null;
            System.out.println(isCompleteBinaryTree(root1));
        }
    }