当前位置:网站首页>958. 二叉树的完全性检验
958. 二叉树的完全性检验
2022-04-23 17:32:00 【hequnwang10】
一、题目描述
示例 1:
输入:root = [1,2,3,4,5,6]
输出:true
解释:最后一层前的每一层都是满的(即,结点值为 {1} 和 {2,3} 的两层),且最后一层中的所有结点({4,5,6})都尽可能地向左。
示例 2:
输入:root = [1,2,3,4,5,null,7]
输出:false
解释:值为 7 的结点没有尽可能靠向左侧。
二、解题
DFS
当前节点N的左子节点的值为2N,右子节点的值为2N+1,每次遍历时统计节点数,和节点的最大值。如果满足完全二叉树,则节点数和最大值相等,否则不相等
class Solution {
//最大值
int maxNum = 0;
//计数节点
int cnt = 0;
public boolean isCompleteTree(TreeNode root) {
//DFS 根节点为N ,左子节点2*N 右子节点 2*N+1;
if(root == null){
return true;
}
dfs(root,1);
return maxNum == cnt;
}
public void dfs(TreeNode root,int curNum){
//终止条件
if(root == null){
return;
}
maxNum = Math.max(maxNum,curNum);
cnt++;
dfs(root.left,2*curNum);
dfs(root.right,2*curNum+1);
}
}
BFS
广度优先遍历。当出现 null 值时停止遍历,如果此时还有没有遍历到的结点,说明该树非完全二叉树。
class Solution {
// 广度遍历二叉树,当出现 null 值时停止遍历,如果此时还有没有遍历到的结点,说明该树非完全二叉树。
public boolean isCompleteTree(TreeNode root) {
Deque<TreeNode> queue = new LinkedList<>();
TreeNode cur;
queue.add(root);
while((cur = queue.poll()) != null){
queue.add(cur.left);
queue.add(cur.right);
}
//判断队列中是否为空
while(!queue.isEmpty()){
if(queue.poll() != null){
return false;
}
}
return true;
}
}
版权声明
本文为[hequnwang10]所创,转载请带上原文链接,感谢
https://blog.csdn.net/hequnwang10/article/details/124331496
边栏推荐
- Learning record of uni app dark horse yougou project (Part 2)
- Signalr can actively send data from the server to the client
- Solution of Navicat connecting Oracle library is not loaded
- JVM class loading mechanism
- freeCodeCamp----shape_ Calculator exercise
- 1-2 JSX syntax rules
- . net type transfer
- ClickHouse-表引擎
- ASP. NET CORE3. 1. Solution to login failure after identity registers users
- Double pointer advanced -- leetcode title -- container with the most water
猜你喜欢
RPC核心概念理解
Deep understanding of control inversion and dependency injection
. net type transfer
Qt error: /usr/bin/ld: cannot find -lGL: No such file or directory
stm32入门开发板选野火还是正点原子呢?
Future 用法详解
双指针进阶--leetcode题目--盛最多水的容器
PC uses wireless network card to connect to mobile phone hotspot. Why can't you surf the Internet
Qt 修改UI没有生效
JVM类加载机制
随机推荐
Shell-sed命令的使用
开期货,开户云安全还是相信期货公司的软件?
The system cannot be started after AHCI is enabled
[simple understanding of database]
练习:求偶数和、阈值分割和求差( list 对象的两个基础小题)
Read software engineering at Google (15)
Shell - introduction, variables, and basic syntax
Net standard
freeCodeCamp----prob_ Calculator exercise
Clickhouse SQL operation
Basic case of Baidu map
1-1 NodeJS
Advantages and disadvantages of several note taking software
ECMAScript history
Wiper component encapsulation
Use of shell cut command
[C#] 彻底搞明白深拷贝
XTask与Kotlin Coroutine的使用对比
1-4 configuration executable script of nodejs installation
Indexes and views in MySQL