[数据结构与算法]00二叉树中等 NC198 判断是不是完全二叉树

NC198 判断是不是完全二叉树

描述

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

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

分析

层级遍历二叉树，当遇到一个结点的孩子为空，则队列里面的结点的孩子都为空，否则就不是完全二叉树。

import java.util.*;
public class Solution {
    public boolean isCompleteTree (TreeNode root) {
        Queue<TreeNode> que = new LinkedList<>();
        if(root == null){
            return true;
        }
        que.offer(root);
        boolean flag = false;
        while(!que.isEmpty()){
            int len = que.size();
            for(int i = 0; i < len; i++){
                TreeNode node = que.poll();
                if(flag && (node.left != null || node.right != null)){
                    return false;
                }
                if(node.left != null){
                    que.offer(node.left);
                }else{
                    flag = true;
                }
                if(flag && node.right != null){
                    return false;
                }
                if(node.right != null){
                    que.offer(node.right);
                }else{
                    flag = true;
                }
            }
        }
        return true;
    }
}