题解 | #判断是不是完全二叉树#

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return bool布尔型
     */
    public boolean isCompleteTree (TreeNode root) {
        // write code here
        if(root==null){
            return true;
        }
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        q.offer(root);
        boolean preHasNull=false;
        while(!q.isEmpty()){
            TreeNode cur = q.poll();
            //遇见空节点，到达最后一层
            if(cur==null){
                preHasNull=true;
                continue;
            }
            //前面已经出现空节点，后面若有非空节点则不是完全二叉树
            if(preHasNull){
                return false;
            }
            //左右孩子入队，不管是否为空，交由下次循环判断
            q.offer(cur.left);
            q.offer(cur.right);
        }
        
        return true;
    }
}

方法：层次遍历（队列）

因为完全二叉树的叶子节点都在最后一层和倒数第二层，空节点后面不会有非空节点，通过将每一层的节点入队，然后判断是否为空，再判断后续节点是否为空就可以判断是否为完全二叉树了。

1、空树为完全二叉树

2、定义一个辅助队列，头结点入队

3、队头出队，判断是否为空，空则作标记。

4、判断标记，若为真代表前面出现了空节点，而能进行到当前步骤说明出现了非空节点，则为非完全

5、最后即标记一直为假，返回true