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

思路：

• 1、根据完全二叉树的特性，如果某个节点无左孩子，则该节点一定不能有右孩子；
• 2、如果某个节点无孩子，则该节点之后的所有节点，都不能有孩子；
• 3、如果某个节点左孩子不为空，但是右孩子为空，则该节点之后的所有节点都不能有孩子；

实现：
对二叉树进行层序遍历，将每一层的节点放入队列中，即对二叉树进行广度优先遍历（BFS），根据上述思路对队列中的每个节点进行判断；
需要增加一个标记位，来标识某个节点之后，是否可以拥有孩子；具体实现和注释见如下代码：

public static boolean isCompleteTree (TreeNode root) {

        if (root == null) {
            return false;
        }
        Queue queue = new LinkedList();
        queue.offer(root);

        //用于记录队列中的后续节点是否还能拥有孩子
        boolean flag = false;
        while(!queue.isEmpty()) {
            int size = queue.size();

            for(int i=0; i<size; i++){
                TreeNode node = queue.poll();

                //左节点为空，但是右节点不空，肯定不是完全二叉树
                if (node.left == null && node.right != null){
                    return false;
                }
                //标志位为true，表示后续节点不能拥有孩子，所以如果有孩子直接返回false
                if (flag && (node.left != null || node.right != null)) {
                    return false;
                }
                //当前节点无孩子，则后续节点同样无孩子
                if (node.left == null && node.right == null) {
                    flag = true;
                }
                //当前节点右节点为空，则后续节点不能有孩子
                if (node.left != null && node.right == null) {
                    flag = true;
                }
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
        }
        return true;
    }