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

import java.util.LinkedList;

/*
 * 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 (null == root.left && null == root.right) { // 如果只有一个根节点，那么这棵树当然是完全二叉树啦
            return true;
        }
        // 定义一个队列
        Queue<TreeNode> queue = new LinkedList<>();
        // 定义一个辅助节点
        TreeNode tmp = root;
        // 定义一个开关
        int sw = 0; // 0：表示关闭    1：表示打开
        // 初始化
        queue.add(tmp);
        // 广度优先遍历
        while (!queue.isEmpty()) { // 队列不为空
           tmp = queue.poll();
            
            // 具体逻辑代码
            // 有一种情况很好判断，那就是完全二叉树中不存在这么一个节点，它有右孩子，但是没有左孩子。如果弹出的这么一个节点是这种情况的，那么这棵树一定不是完全二叉树
            if (null == tmp.left && null != tmp.right) {
                return false;
            }
            // 还有一种情况就是，如果出现了一个只有左孩子但是没有右孩子的节点，那么接下来所有的节点都是叶子节点
            if (sw == 0) { // sw 为 0，意味着开关处于关闭状态
                if ((null != tmp.left && null == tmp.right) || (null == tmp.left && null == tmp.right))
                {
                    sw = 1; // 将 sw 置为 1，意味着，后续的节点必须都是叶子节点，否则返回 false
                }
                else {
                    // 这就是其它正常的节点，没啥好操作的
                }
            }
            else if (sw == 1) { // sw 为 1，意味着开关已经被打开了，接下里所有的节点都要为叶子节点
                if (null == tmp.left && null == tmp.right) {
                    // 这就是其它正常的节点，没啥好操作的
                    continue;
                }
                else {
                    return false;
                }
            }
            
            if (null != tmp.left) { // 如果左孩子不为空，那么将左孩子入队列
                queue.add(tmp.left);
            }
            if (null != tmp.right) { // 如果右孩子不为空，那么将右孩子入队列
                queue.add(tmp.right);
            }
        }
        return true;
    }
}