首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LeetCode 958. 二叉树的完全性检验(层序遍历)

LeetCode 958. 二叉树的完全性检验(层序遍历)

作者头像
Michael阿明
发布2020-07-13 16:06:46
3390
发布2020-07-13 16:06:46
举报

1. 题目

给定一个二叉树,确定它是否是一个完全二叉树。

百度百科中对完全二叉树的定义如下:

若设二叉树的深度为 h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。(注:第 h 层可能包含 1~ 2h 个节点。)

示例 1:
在这里插入图片描述
在这里插入图片描述
输入:[1,2,3,4,5,6]
输出:true
解释:最后一层前的每一层都是满的(即,结点值为 {1} 和 {2,3} 的两层),
且最后一层中的所有结点({4,5,6})都尽可能地向左。
示例 2:
在这里插入图片描述
在这里插入图片描述
输入:[1,2,3,4,5,null,7]
输出:false
解释:值为 7 的结点没有尽可能靠向左侧。
 
提示:
树中将会有 1 到 100 个结点。

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/check-completeness-of-a-binary-tree 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

2. 层序遍历

  • 利用队列层序遍历,注意对子节点为空的话,也把它加入队列
  • 当遇见NULL出队时,后面再遇见非空节点出队,则说明不是完全二叉树
class Solution {
public:
    bool isCompleteTree(TreeNode* root) {
   		bool hasNULL = false;
   		queue<TreeNode*> q;
   		q.push(root);
   		TreeNode *tp;
   		while(!q.empty())
   		{
   			tp = q.front();
   			q.pop();
   			if(hasNULL && tp != NULL)//有NULL出队了,且现在出队的非空
   				return false;
   			if(tp == NULL)
   				hasNULL = true;
   			else
   			{
	   			q.push(tp->left);
	   			q.push(tp->right);
	   		}
   		}
   		return true;
    }
};
在这里插入图片描述
在这里插入图片描述
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2019-11-16 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 1. 题目
  • 2. 层序遍历
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档