二叉树 - 958.二叉树的完全性检验

给定一个二叉树的 root ，确定它是否是一个完全二叉树 。

在一个完全二叉树中，除了最后一个关卡外，所有关卡都是完全被填满的，并且最后一个关卡中的所有节点都是尽可能靠左的。

输入：root = [1,2,3,4,5,6]
输出：true
解释：最后一层前的每一层都是满的（即，结点值为 {1} 和 {2,3} 的两层），且最后一层中的所有结点（{4,5,6}）都尽可能地向左。

解题思路：层序遍历

• 如果树为空，返回false
• 如果树不为空，开始层序遍历二叉树（用队列）

对于一个完全二叉树，层序遍历的过程中遇到第一个空节点之后不应该再出现非空节点

class Solution {
    public boolean isCompleteTree(TreeNode root) {
        if(root == null) return false;
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        boolean firstNull = false;
        while(!queue.isEmpty()) {
            TreeNode node = queue.poll();
            // 遇到第一个空节点之后不应该再出现非空节点
            if(firstNull && node != null) {
                return false;
            }
            if(node == null) {
                // 标记第一个空节点
                firstNull = true;
                continue;
            }
            queue.offer(node.left);
            queue.offer(node.right);
        }
        return true;
    }
}