赞
踩
题目来源:牛客网 BM35 判断是不是完全二叉树
给定一个二叉树,确定他是否是一个完全二叉树。
完全二叉树的定义:若二叉树的深度为 h h h,除第 h h h层外,其它各层的结点数都达到最大个数,第 h h h层所有的叶子结点都连续集中在最左边,这就是完全二叉树。(第 h h h层可能包含[1-2h]个节点)
数据范围:节点数满足
1
≤
n
≤
100
1\le n \le 100
1≤n≤100
样例图1:
样例图2:
样例图3:
示例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
知识点:队列
队列是一种仅支持在表尾进行插入操作、在表头进行删除操作的线性表,插入端称为队尾,删除端称为队首,因整体类似排队的队伍而得名。它满足先进先出的性质,元素入队即将新元素加在队列的尾,元素出队即将队首元素取出,它后一个作为新的队首。
思路
对完全二叉树最重要的定义就是叶子节点只能出现在最下层和次下层,所以我们想到可以使用队列辅助进行层次遍历——从上到下遍历所有层,每层从左到右,只有次下层和最下层才有叶子节点,其他层出现叶子节点就意味着不是完全二叉树。
具体做法:
Java
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 curr; // 定义一个首次出现的标记位 boolean not Complete = false; while(!queue.isEmpty()){ curr = queue.poll(); // 标记第一次遇到空节点 if(curr==null){ notComplete = true; continue; } if(notComplete){ return false; } queue.offer(curr.left); queue.offer(curr.right); } return true; } }
python
# -*- coding: utf-8 -*-# # ---------------------------------------------- # Name: BM35.py # Description: 判断是不是完全二叉树 # Author: PANG # Date: 2022/7/11 # ---------------------------------------------- class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None import queue class Solution: def isCompleteTree(self, root: TreeNode) -> bool: if not root: return True q = queue.Queue() q.put(root) # 定义一个首次数显的标记位 flag = False # 层次遍历 while not q.empty(): sz = q.qsize() for i in range(sz): curr = q.get() # 标记第一次遇到的空节点 if not curr: flag = True else: if flag: return False q.put(curr.left) q.put(curr.right) return True
复杂度分析
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。