272、二叉树的完全性检验
程序员文章站
2022-03-23 17:54:56
...
题目描述:
给定一个二叉树,确定它是否是一个完全二叉树。
百度百科中对完全二叉树的定义如下:
若设二叉树的深度为 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
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
我一开始的思路比较复杂了,先算出二叉树的层高,然后我们逐层遍历,遇见倒数第二层时需要注意
代码中写的比较冗余
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isCompleteTree(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
int dep = getdep(root) - 1;
queue.offer(root);
int curdep = 0;
while (!queue.isEmpty()){
if(curdep == dep){
return true;
}
int size = queue.size();
if(curdep < dep - 1){
for (int i = 0; i < size; i++) {
TreeNode poll = queue.poll();
if(poll.left == null || poll.right == null){
return false;
}
queue.offer(poll.left);
queue.offer(poll.right);
}
// curdep ++;
}else{
boolean flag = true;
for (int i = 0; i < size; i++) {
TreeNode poll = queue.poll();
if(poll.right != null && poll.left == null){
return false;
}
// 前方出现有一个
if((poll.left != null || poll.right != null) && !flag){
return false;
}
if((poll.left != null && poll.right == null) || (poll.left == null && poll.right == null)){
flag = false;
}
if(poll.left != null){
queue.offer(poll.left);
}
if(poll.right != null){
queue.offer(poll.right);
}
}
// curdep ++;
}
curdep ++;
}
return false;
}
public int getdep(TreeNode root){
if(root == null){
return 0;
}
int left = getdep(root.left);
int right = getdep(root.right);
return Math.max(left,right) + 1;
}
}
看看别人实现的,简单明了
其实很简单,只要遍历到null节点,看后面有没有了,如果还有就返回false,否则为true
class Solution {
/**
* 广度遍历二叉树,当出现 null 值时停止遍历,如果此时还有没有遍历到的结点,说明该树非完全二叉树。
*/
public boolean isCompleteTree(TreeNode root) {
LinkedList<TreeNode> q = new LinkedList<>();
TreeNode cur;
q.addLast(root);
while ((cur = q.removeFirst()) != null) {
q.addLast(cur.left);
q.addLast(cur.right);
}
while (!q.isEmpty()) {
if (q.removeLast() != null) {
return false;
}
}
return true;
}
}
上一篇: php5.2安装教程分享
推荐阅读
-
LeetCode第958题 二叉树的完全性检验
-
958. 二叉树的完全性检验
-
Leetcode刷题记录——958. 二叉树的完全性检验
-
leetcode 第 958 题:二叉树的完全性检验(C++)
-
leetcode 958 二叉树的完全性检验(超简洁写法)
-
leetcode 958. 二叉树的完全性检验(输出是否是完全二叉树 dfs/bfs每次假如队列的时候判断 值是不是sz)
-
给定两个非空二叉树 s 和 t,检验s 中是否包含和 t 具有相同结构和节点值的子树
-
二叉树的完全性检验——Python实现(BFS)
-
272、二叉树的完全性检验
-
给定两个非空二叉树 s 和 t,检验s 中是否包含和 t 具有相同结构和节点值的子树