每日算法之判断是不是平衡二叉树
2023-03-31 10:42:23 时间
JZ79 判断是不是平衡二叉树
描述
输入一棵节点数为 n 二叉树,判断该二叉树是否是平衡二叉树。
在这里,我们只需要考虑其平衡性,不需要考虑其是不是排序二叉树
平衡二叉树(Balanced Binary Tree),具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。
思路
左右两个子树的高度差的绝对值不超过1
左右两个子树都是一棵平衡二叉树
代码
package esay.JZ79判断是不是平衡二叉树;
class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
public class Solution {
//自顶向下
/*public boolean IsBalanced_Solution(TreeNode root) {
//空树也是平衡二叉树
if (root == null) return true;
//左子树深度
int left = deep(root.left);
//右子树深度
int right = deep(root.right);
if (left - right > 1 || right - left > 1) return false;
return IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
}
public int deep (TreeNode node) {
if (node == null) return 0;
//左遍历
int left = deep(node.left);
//右遍历
int right = deep(node.right);
return left > right ? left + 1 :right + 1;
}*/
//自底向上
public boolean IsBalanced_Solution(TreeNode root) {
if (root == null) return true;
return getdepth(root) != -1;
}
public int getdepth (TreeNode node) {
if (node == null) return 0;
//左遍历
int left = getdepth(node.left);
if (left < 0) return -1;
//右遍历
int right = getdepth(node.right);
if (right < 0) return -1;
return Math.abs(left - right) > 1 ? -1 : Math.max(left, right) + 1;
}
}
相关文章
- 金融服务领域的大数据:即时分析
- 影响大数据、机器学习和人工智能未来发展的8个因素
- 从0开始构建一个属于你自己的PHP框架
- 如何将Hadoop集成到工作流程中?这6个优秀实践必看
- SEO公司使用大数据优化其模型的5种方法
- 关于Web Workers你需要了解的七件事
- 深入理解HTTPS原理、过程与实践
- 增强分析:数据和分析的未来
- PHP协程实现过程详解
- AI专家:大数据知识图谱——实战经验总结
- 关于PHP的错误机制总结
- 利用数据分析量化协同过滤算法的两大常见难题
- 怎么做大数据工作流调度系统?大厂架构师一语点破!
- 2019大数据处理必备的十大工具,从Linux到架构师必修
- OpenCV中的KMeans算法介绍与应用
- 教大家如果搭建一套phpstorm+wamp+xdebug调试PHP的环境
- CentOS下三种PHP拓展安装方法
- Go语言HTTP Server源码分析
- Go语言HTTP Server源码分析
- 2017年4月编程语言排行榜:Hack首次进入前五十