LeetCode第110题:平衡二叉树
2024-10-21 11:43:21
问题描述
给定一个二叉树,判断它是否是高度平衡的二叉树。
本题中,一棵高度平衡二叉树定义为:
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
示例 1:
给定二叉树 [3,9,20,null,null,15,7]
3
/
9 20
/
15 7
返回 true 。
示例 2:
给定二叉树 [1,2,2,3,3,null,null,4,4]
1
/ \
2 2
/ \
3 3
/
4 4
返回 false 。
解题思路
很明显的用递归思路可以解决,不过这样的算法效率并不是很高,因为每个节点会被遍历很多次。
递归解法
首先判定二叉树是否平衡还需要一个求节点高度的函数。
再之后就是套平衡二叉树的定义,空树是平衡二叉树,每个节点左右子树高度之差绝对值不超过1的也是平衡二叉树。
当左右子树都平衡时,进一步判断当前节点是否平衡。
当左右子树不都平衡时,显然不是平衡二叉树。
非递归解法
待完善
C++代码
递归解法
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isBalanced(TreeNode* root) {
//空子树是平衡二叉树
if(root==nullptr)
return true;
//左右子树全平衡
//进一步判断当前节点是否平衡
if(isBalanced(root->left)&&isBalanced(root->right)){
int leftHeight=height(root->left);
int rightHeight=height(root->right);
int factor=abs(leftHeight-rightHeight);
return factor>-1&&factor<2?true:false;
}
//左右子树不全平衡
return false;
}
//计算二叉树的高度
int height(TreeNode* root){
//空指针高度为0
if(root==nullptr)
return 0;
//否则当前节点高度为
//左右子树高度最大值+1
int leftHeight=height(root->left);
int rightHeight=height(root->right);
return leftHeight>rightHeight?leftHeight+1:rightHeight+1;
}
};
非递归解法
待完善
执行结果
递归解法
非递归解法
待完善
最新文章
- MySQL监控系统MySQL MTOP的搭建
- Ruby用法总结
- maven web项目不能创建src/main/java等文件夹的问题
- 如何启用Service,如何停用Service
- Centos 7 python升级(2.7.5-》2.7.11)
- 转载:NSobject官方介绍
- 让C#、VB.NET实现复杂的二进制操作
- 新版MATERIAL DESIGN 官方动效指南(二)
- C++中重载、覆盖与隐藏的区别(转)
- bootstrap轮播图 两侧半透明阴影
- ASP.NET Core 新建线程中使用依赖注入的问题
- [TJOI2018]教科书般的亵渎
- 五,mysql优化——sql语句优化小技巧
- 对threading模块源码文件的解读(不全)
- python中模块导入问题(已解决)
- 对Java ConcurrentHashMap的一些了解
- Elasticsearch之停用词
- Qt精简编译方法总结
- thinkphp 编辑器kindeditor
- mysql中开启慢查询日志