00二叉树中等 NC198 判断是不是完全二叉树

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;}
}