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

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) {
        // 完全二叉树的特点：
        //1. 除了最后一层，其他层的节点数必须达到最大
        //2. 最后一层的节点必须从左到右连续排列，不能有空缺
        // 思路： 使用队列进行层序遍历。在遍历过程中，如果遇到一个空节点，则后续所有节点都必须是空节点。如果在遇到了空节点后，又发现了非空节点，则说明这棵树不是完全二叉树。
        if(root == null){
            //空树是完全二叉树
            return true;
        }

        Queue<TreeNode> q = new LinkedList<TreeNode>();
        q.offer(root);
        boolean hasNull = false;//标记是否遇到过空节点

        while(!q.isEmpty()){
            TreeNode node = q.poll();

            if(node == null){
                hasNull = true;//遇到空节点，标记为true
            }else{
                //如果之前已经遇到过空节点，但当前节点不是空节点，则说明不是完全二叉树
                if(hasNull){
                    return false;
                }
                //将左右子节点加入队列
                q.offer(node.left);
                q.offer(node.right);
            }
        }

        return true;
    }
}

解题思路：首先需要了解完全二叉树的定义和特点：1. 除了最后二叉树的一层，其他层的节点数必须达到最大；2. 最后一层的节点必须从左到右连续排列，其中不能有空缺。因此基于以上特性，我们可以联想到使用层序遍历，而不是树的前中后序遍历来检查是否满足完全二叉树的条件。

层序遍历：层序遍历即为按照层检查节点，以此确保每一层节点都从左到右连续排列。

队列：队列具有先进先出（FIFO）的特性，因此相对于其他的数据结构，更适合实现层序遍历。

算法思路：

1. 首先判断传入数据的有效性，判断空树是否为完全二叉树。

2. 将根节点入队offer(root)。并设置一个布尔变量hasNull，用于记录在出队过程中是否有空节点存在。

3. 一边将根节点的左右节点入队，一边判断出队节点是否为空节点。若为空节点，则记录hasNull =true。并在后续出队节点中判断是否还有非空节点存在。如果存在则直接返回false。

4. 直至将一颗二叉树完全遍历结束后，则返回true。说明该树的每一层节点都按照从左到右连续排列，且其中无空缺。是一颗完全二叉树。