#yyds干货盘点# 面试必刷TOP101：判断是不是完全二叉树

1.简述：

描述

给定一个二叉树，确定他是否是一个完全二叉树。

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

数据范围：节点数满足 

样例图1：

样例图2：

样例图3：

示例1

输入：

{1,2,3,4,5,6}

返回值：

true

示例2

输入：

{1,2,3,4,5,6,7}

返回值：

true

示例3

输入：

{1,2,3,4,5,#,6}

返回值：

false

2.代码实现：

import java.util.*;
public class Solution {
public boolean isCompleteTree (TreeNode root) {
//空树一定是完全二叉树
if(root == null)
return true;
//辅助队列
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
TreeNode cur;
//定义一个首次出现的标记位
boolean notComplete = false;
while(!queue.isEmpty()){
cur = queue.poll();
//标记第一次遇到空节点
if(cur == null){
notComplete = true;
continue;
}
//后续访问已经遇到空节点了，说明经过了叶子
if(notComplete)
return false;
queue.offer(cur.left);
queue.offer(cur.right);
}
return true;
}
}