Check If Binary Tree Is Completed
2024-09-07 10:05:02
Check if a given binary tree is completed. A complete binary tree is one in which every level of the binary tree is completely filled except possibly the last level. Furthermore, all nodes are as far left as possible.
Examples
5
/ \
3 8
/ \
1 4
is completed.
5
/ \
3 8
/ \ \
1 4 11
is not completed.
Corner Cases
- What if the binary tree is null? Return true in this case.
How is the binary tree represented?
We use the level order traversal sequence with a special symbol "#" denoting the null node.
For Example:
The sequence [1, 2, 3, #, #, 4] represents the following binary tree:
1
/ \
2 3
/
4
/**
* public class TreeNode {
* public int key;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int key) {
* this.key = key;
* }
* }
*/
public class Solution {
public boolean isCompleted(TreeNode root) {
// Write your solution here
if (root==null){
return true;
}
Queue<TreeNode> q = new LinkedList<TreeNode>();
q.offer(root); int isLeaf = 0;
while(!q.isEmpty()){
Queue<TreeNode> nextQ = new LinkedList<TreeNode>();
int size = q.size();
for(int i=0; i<size; i++){
TreeNode curNode = q.poll();
if(curNode.left==null && curNode.right!=null){
return false;
}
if(curNode.left!=null){
if(isLeaf==1){
return false;
}
nextQ.offer(curNode.left);
}
if(curNode.right!=null){
if(isLeaf==1){
return false;
}
nextQ.offer(curNode.right);
}
if(curNode.left==null || curNode.right==null){
isLeaf=1;
}
}
q = nextQ;
}
return true; }
}
最新文章
- MYSQL中UNIX时间戳与日期的转换
- 1 Ionic和Hybird应用介绍
- Python: 拷贝函数签名
- 黑客入门之IP地址及常用命令
- TCPCopy 应用
- java中equals和hashCode方法的解析
- MapReduce shuffle阶段详解
- 过度拟合（overfitting）
- RADIUS and IPv6[frc-3162译文]
- linux下Nginx配置文件(nginx.conf)配置设置详解（windows用phpstudy集成）
- Nagios学习实践系列
- 02_HTML5+CSS详解第二天
- MongoDB 高级索引
- C++: 模板函数定义与声明分离；
- appium-doctor问题
- 巩固python基础
- vsftp 基于虚拟用户的ftp服务器 如何做配额
- Django学习手册 - 正则URL路由配置/路由分发
- 2018.10.20 bzoj1068: [SCOI2007]压缩（区间dp）
- JVM基础知识与配置