Leetcode958. Check Completeness of a Binary Tree二叉树的完全验证性
2024-09-02 13:33:06
给定一个二叉树,确定它是否是一个完全二叉树。
百度百科中对完全二叉树的定义如下:
若设二叉树的深度为 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 个结点。
个人递归方法:
class Solution {
bool isTheEnd = false;
int depth = 0;
public:
bool isCompleteTree(TreeNode* root)
{
if (root == NULL)
return true;
depth = GetDepth(root);
return GetAns(root, 1);
}
int GetDepth(TreeNode *root)
{
if (root == NULL)
return 0;
return max(GetDepth(root->left), GetDepth(root->right)) + 1;
}
bool GetAns(TreeNode *root, int dep)
{
//只有根节点的情况,不用判空,因为不会递归到那
if (dep == depth)
{
return true;
}
if (dep < depth - 1)
{
if (root->left == NULL || root->right == NULL)
return false;
return GetAns(root->left, dep + 1) && GetAns(root->right, dep + 1);
}
else if (dep == depth - 1)
{
if (isTheEnd)
{
if (root->left != NULL || root->right != NULL)
return false;
return true;
}
else
{
if (root->left == NULL)
{
if (root->right != NULL)
return false;
isTheEnd = true;
return true;
}
if (root->right == NULL)
{
isTheEnd = true;
return true;
}
return true;
}
}
}
};
广度优先遍历法(推荐):
bool isCompleteTree(TreeNode* root) {
queue<TreeNode *> que;
que.push(root);
while(!que.empty())
{
TreeNode * node = que.front();
que.pop();
if(!node)
{
break;
}
else
{
que.push(node->left);
que.push(node->right);
}
}
while(!que.empty())
{
TreeNode * node=que.front();
if(node)
return false;
que.pop();
}
return true;
}
最新文章
- 设计模式(十):从电影院中认识";迭代器模式";(Iterator Pattern)
- make: *** [out/host/linux-x86/obj/EXECUTABLES/aidl_intermediates/aidl] 错误 1,make: *** [out/host/linux-x86/obj/lib/libESR_Portable.so] 错误 1
- asp.net mvc5 伪静态
- Android中的Activity相关知识总结
- TopCoder
- SQL Server 2005中的分区表(二):如何添加、查询、修改分区表中的数据(转)
- 【五】PHP数组操作函数
- C#调用R语言输出图片
- FindLetter 类——查找文件中特定的字符,每一行开头为某一个字符,则跳过
- outlook 当关闭时最小化到任务栏完美的解决方案
- opencv----彩色图像对比度增强
- Java课程设计——GUI密码生成器201521123035
- Java虚拟机学习笔记——JVM垃圾回收机制
- Python3 tkinter基础 Menu Frame 创建右键菜单
- stenciljs 学习十一 pwa 支持
- jquery综合练习--模态对话框传值,删除,新增表格行
- devise在引擎中安装后,设置访问自定义页面
- JAVA在语言级支持多线程
- poj 2229 Sumsets 完全背包求方案总数
- 15 Django组件-中间件
热门文章
- soapui打开即报错------连接不上Internet
- 贪心+MST——cf1095F
- (转)JNI入门教程之HelloWorld篇 .
- 牛客多校第五场 G subsequence 1 最长公共子序列/组合数
- .net core, docker 在vs2019开发过程中的问题以及解决办法
- angluar1.8.2 PC Mail项目笔记
- private变量引用问题
- 第二篇:怕碰到是因为没掌握,来吧,zTree!
- <;每日一题>;算法题:小球的下落距离
- 透视jvm之垃圾回收