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

哈妹 lv.1

发布时间：2022-09-22 22:30:50 342

相关标签： # java# java# 数据

1.简述：

描述

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

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

数据范围：节点数满足

样例图1：

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

样例图2：

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

样例图3：

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

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

文章来源： https://blog.51cto.com/u_15488507/5628193

特别声明：以上内容（图片及文字）均为互联网收集或者用户上传发布，本站仅提供信息存储服务！如有侵权或有涉及法律问题请联系我们。