题目描述
给定一个二叉树，确定他是否是一个完全二叉树。
完全二叉树的定义：若二叉树的深度为 h，除第 h 层外，其它各层的结点数都达到最大个数，第 h 层所有的叶子结点都连续集中在最左边，这就是完全二叉树。（第 h 层可能包含 [1~2h] 个节点）
示例
- 示例1
示例1
输入：{1,2,3,4,5,6}
输出：true - 示例2
示例2
输入：{1,2,3,4,5,#,6}
输出：false
思路方法
利用队列，将二叉树的所有节点记录下来。
根据完全二叉树的特性，当第一次遇到null节点的时候，就不会再有后续节点。
所以当遇到null后，队列仍然有非null节点弹出的话，就说明该二叉树不是完全二叉树。
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) {
// write code here
//空子树一定是二叉树
if(root==null){
return true;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
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;
}
}
