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

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 {
    public boolean isCompleteTree (TreeNode root) {
        if(root == null)
            return true;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        TreeNode cur;
        boolean notComplete = false;
        
        while(!queue.isEmpty()){
            cur = queue.poll();
            if(cur == null){
                notComplete = true;
                continue;
            }
            if(notComplete)
                return false;
            //此题与层序遍历不一样的点，没有判断左右子树是否为空，经过草稿纸上画图可以得知：
            //如果是完全二叉树，那么当层序遍历出现空节点时，一定能保证此空节点是第在h层
            //因为是从左往右遍历，当出现空结点之后，后续不可能再出现非空节点，否则就说明：
            //左子树空而右子树非空，或者是叶子节点不仅仅位于h层和h-1层，这样都可以判断完全二叉树
            queue.offer(cur.left);
            queue.offer(cur.right);
        }
        return true;
    }
}