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

思路

1. 层次遍历，遍历结果内部没有空即为完全二叉树
2. 判断为空可以用如下方法：
   • 第一次遇到null，设置res为true，假设一个完全二叉树的有效节点已经遍历结束，只剩空结点
   • 继续遍历如果遇到非空结点，则假设不成立，直接返回false
   • 否则直至结束都是空结点，则假设成立，返回res，即true

   代码

public class Solution {
    public boolean isCompleteTree (TreeNode root) {
        return levelOrder(root);
    }

    public boolean levelOrder(TreeNode root){
        Queue<TreeNode> q=new LinkedList<>();
        q.offer(root);
        boolean res=false;
        //层次遍历框架
        while(!q.isEmpty()){
            int size=q.size();
            for(int i=0;i<size;i++){
                TreeNode now=q.poll();
                //遇到空则假设当前有效结点已经遍历结束，设置res为true
                if(now==null) res=true;
                else{
                	//再遇到非空结点（且res为true）则假设不成立，返回false
                    if(res) return false;
                    q.offer(now.left);
                    q.offer(now.right);
                }
            }
        }
        return res;
    }
}