当前位置:网站首页>958. Complete binary tree test
958. Complete binary tree test
2022-04-23 17:33:00 【hequnwang10】
One 、 Title Description
Example 1:
Input :root = [1,2,3,4,5,6]
Output :true
explain : Every floor before the last floor is full ( namely , The node value is {1} and {2,3} The two layers ), And all nodes in the last layer ({4,5,6}) As far left as possible .
Example 2:
Input :root = [1,2,3,4,5,null,7]
Output :false
explain : The value is 7 The node of is not as far to the left as possible .
Two 、 Problem solving
DFS
Current node N The value of the left child node of is 2N, The value of the right child node is 2N+1, Count the number of nodes during each traversal , And the maximum value of the node . If a complete binary tree is satisfied , Then the number of nodes and the maximum value are equal , Otherwise it's not equal
class Solution {
// Maximum
int maxNum = 0;
// Counting node
int cnt = 0;
public boolean isCompleteTree(TreeNode root) {
//DFS The root node is N , The left child node 2*N The right child node 2*N+1;
if(root == null){
return true;
}
dfs(root,1);
return maxNum == cnt;
}
public void dfs(TreeNode root,int curNum){
// Termination conditions
if(root == null){
return;
}
maxNum = Math.max(maxNum,curNum);
cnt++;
dfs(root.left,2*curNum);
dfs(root.right,2*curNum+1);
}
}
BFS
Breadth first traversal . When there is a null Stop traversal on value , If there are nodes that have not been traversed at this time , It shows that the tree is not a complete binary tree .
class Solution {
// Breadth traversal binary tree , When there is a null Stop traversal on value , If there are nodes that have not been traversed at this time , It shows that the tree is not a complete binary tree .
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);
}
// Judge whether the queue is empty
while(!queue.isEmpty()){
if(queue.poll() != null){
return false;
}
}
return true;
}
}
版权声明
本文为[hequnwang10]所创,转载请带上原文链接,感谢
https://yzsam.com/2022/04/202204231732009375.html
边栏推荐
- Router object, route object, declarative navigation, programmed navigation
- ASP. Net core configuration options (Part 2)
- Collection of common SQL statements
- 470. 用 Rand7() 实现 Rand10()
- Using quartz under. Net core -- job attributes and exceptions of [4] jobs and triggers
- Net standard
- flink 学习(十二)Allowed Lateness和 Side Output
- 超分之TDAN
- 索引:手把手教你索引从零基础到精通使用
- Self use learning notes - connectingstring configuration
猜你喜欢
Learning record of uni app dark horse yougou project (Part 2)
Flash project cross domain interception and DBM database learning [Baotou cultural and creative website development]
EF core in ASP Generate core priority database based on net entity model
线性代数感悟之2
Matlab / Simulink simulation of double closed loop DC speed regulation system
嵌入式系统中,FLASH中的程序代码必须搬到RAM中运行吗?
C语言函数详解
快时钟同步慢时钟域下的异步控制信号slow clk to fast clk
470. 用 Rand7() 实现 Rand10()
958. 二叉树的完全性检验
随机推荐
. net cross platform principle (Part I)
嵌入式系统中,FLASH中的程序代码必须搬到RAM中运行吗?
【WPF绑定3】 ListView基础绑定和数据模板绑定
The system cannot be started after AHCI is enabled
Summary of common SQL statements
Shell-awk命令的使用
SiteServer CMS5. 0 Usage Summary
Node template engine (EJS, art template)
Devexpress GridView add select all columns
为什么有些人说单片机简单,我学起来这么吃力?
node中,如何手动实现触发垃圾回收机制
.Net Core3. 1 use razorengine NETCORE production entity generator (MVC web version)
C# Task. Delay and thread The difference between sleep
Compare the performance of query based on the number of paging data that meet the query conditions
Use of shell sed command
Using quartz under. Net core -- general properties and priority of triggers for [5] jobs and triggers
Use of shell awk command
Shell-cut命令的使用
Excel quickly and automatically fills the contents of a row on a blank cell
剑指 Offer 03. 数组中重复的数字