牛客每日刷题之二叉树

✅作者简介：我是18shou，一名即将秋招的java实习生

✨个人主页：_18shou

🔥系列专栏：牛客刷题专栏

📃推荐一款模拟面试、刷题神器👉 在线刷题面经模拟面试

目录

描述

​编辑

思路

题解

​编辑

复杂度

📃结语

---

描述

给定- -个二叉树，确定他是否是一个完全二 叉树。
完全3二叉树的定义:若_ -叉树的深度为h,除第h层外，其它各层的结点数都达到最大个数,第h层所有的叶子结点都连续集中在最左边，这就是
完全-叉树。(第h层可能包含 [1~2h]个节点)
数据范围:节点数满足1≤n≤100

 

 

思路

方法:层次遍历(推荐使用)
知识点:队列
队列是一种仅支持在表尾进行插入操作、 在表头进行删除操作的线性表，插入端称为队尾，删除端称为队首，因整体类似排队的队伍而得名。它满
足先进先出的性质，元素入队即将新元素加在队列的尾，元素出队即将队首元素取出，它后-个作为新的队首。
思路:
对完全二叉树最重要的定义就是叶子节点只能出现在最下层和次下层，所以我们想到可以使用队列辅助进行层次遍历一从 上到下遍历所有层，每
层从左到右，只有次下层和最下层才有叶子节点，其他层出现叶子节点就意味着不是完全二叉树。
具体做法:
●step 1:先判断空树一定是完全二 叉树。
●step 2:初始化一个队列辅助层次遍历，将根节点加入。
●step 3:逐渐从队列中弹出元素访问节点，如果遇到某个节点为空，进行标记，代表到了完全=叉树的最下层，若是后续还有访问，则说明提
前出现了叶子节点，不符合完全二叉树的性质。
●step4:否则，继续加入左右子节点进入队列排队,等待访问。

题解

import java.util.*;
public class Solution {
    public boolean isCompleteTree (TreeNode root) {
        //空树一定是完全二叉树
        if(root == null) 
            return true;
        //辅助队列
        Queue<TreeNode> 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;
    }
}

 

复杂度

●时间复杂度:
0(n),其中n为二叉树节点数,层次遍历最坏情况下遍历每一个节虑
.空间复杂度: 0(n),最坏情况下,层次队列的最大空间为O(n)

📃结语

兄弟们，一起来刷题👉嘎嘎的写题