【958】完全二叉树

题目（难度：中等）：

若设二叉树的深度为 h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。（注：第 h 层可能包含 1~ 2h 个节点。）

示例 1：

输入：[1,2,3,4,5,6]
输出：true

代码思想：

• 任何一个节点有右孩子没有左孩子，则返回false
• 如果左右孩子不全，即有左孩子无右孩子或者左右均为空，则该节点必为叶子节点，否则返回false

代码思想：

public boolean isCompleteTree(TreeNode root) {
        if (root == null) return true;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        boolean leaf = false;
        while (!queue.isEmpty()) {
            root = queue.poll();
            if (leaf && (root.left != null || root.right != null) || root.left == null && root.right != null) {
                return false;
            }
            if (root.left != null) {
                queue.offer(root.left);
            }
            if (root.right != null) {
                queue.offer(root.right);
            }
            if (root.left == null || root.right == null) {
                leaf = true;
            }
        }
        return true;
    }

测试用例：

算法分析：

时间复杂度O(n)，使用队列，额外空间复杂度O(n)