当前位置: 首页 > news >正文

[java/力扣110]平衡二叉树——优化前后的两种方法

分析

根据平衡二叉树的定义,只需要满足:1、根节点两个子树的高度差不超过1;2、左右子树都为平衡二叉树

代码

public class BalancedBinaryTree {public class TreeNode{int val;TreeNode left;TreeNode right;TreeNode(){}TreeNode(int val){this.val = val;}}public boolean isBalanced(TreeNode root) {if(root == null){return true;}//判断左子树是否为平衡二叉树int leftH = getHeight(root.left);//判断右子树是否为平衡二叉树int rightH = getHeight(root.right);//当满足三个条件时返回turereturn Math.abs(leftH-rightH)<2&&isBalanced(root.left)&&isBalanced(root.right);}//获取树的高度public int getHeight(TreeNode root){if(root == null){return 0;}//获取左子树高度int leftH = getHeight(root.left);//获取右子树高度int rightH = getHeight(root.right);//返回左右子树的最大值+1(加上根节点高度),即为树的高度return ((leftH > rightH) ? (leftH+1):(rightH+1));}
}

进行优化

但是这样的做法,每对一个结点进行平衡判定就要求一次 以该结点为根节点的树的高度。时间复杂度太大

所以我们在求高度的时候就进行判定是否平衡。 


在求高度的时候就进行平衡判定,如果其中一颗子树不平衡,就直接返回-1(因为高度是不能为-1的),子树为空则返回0。

如下图所示。对于3为根节点的二叉树,左树返回1,右树返回0;然后对于9为根节点的二叉树,左子树返回2,右子树返回0;对于以3为根节点的二叉树,左子树返回-1(说明左子树不平衡),右子树返回-1(说明右子树不平衡),所以以3为根节点的二叉树返回-1.

同时要注意:存在一个根节点,其左子树不平衡返回-1,右子树为空返回0,但此时左右子树高度差的绝对值还是1.所以我们要对此做出限制

 优化后的代码

public class Test3 {public class TreeNode{int val;TreeNode left;TreeNode right;TreeNode(){}TreeNode(int val){this.val = val;}}public boolean isBalanced(TreeNode root) {return getHeight(root) >= 0;}//获取树的高度public int getHeight(TreeNode root){if(root == null){return 0;}//获取左子树高度int leftH = getHeight(root.left);//获取右子树高度int rightH = getHeight(root.right);/*如果一个节点左树不平衡(返回-1),右树为空(返回0)。它不是个平衡二叉树,但是它满足左右子树高度差为1* 所以这里限制左右子树高度都大于0*/if (leftH >= 0 && rightH >= 0 &&Math.abs(leftH - rightH)<=1){return Math.max(leftH,rightH)+1;}else {return -1;}/*为什么不能在第一个不平衡的二叉树出现时就结束?* 因为你是判断高度的方法,不是判断平衡的方法。* false应该在另一个方法中被返回*/}
}

http://www.lryc.cn/news/212345.html

相关文章:

  • 吉他、班卓琴和贝斯吉他降分器:Arobas Music Guitar 8.1.1
  • cocos tilemap的setTileGIDAt方法不实时更新
  • 机器学习---使用 TensorFlow 构建神经网络模型预测波士顿房价和鸢尾花数据集分类
  • 铁合金电炉功率因数补偿装置设计
  • 表格识别软件:科技革新引领行业先锋,颠覆性发展前景广阔
  • 【Redis】高并发分布式结构服务器
  • 微信小程序拍照页面自定义demo
  • 单目标应用:进化场优化算法(Evolutionary Field Optimization,EFO)求解微电网优化MATLAB
  • 推荐算法面试
  • 长图切图怎么切
  • 动手学深度学习 - 学习环境配置
  • 洛谷 B2004 对齐输出 C++代码
  • seccomp学习 (1)
  • Linux指令【上】
  • RK3568-clock
  • 新恶意软件使用 MSIX 软件包来感染 Windows
  • 干货!数字IC后端入门学习笔记
  • 力扣:144. 二叉树的前序遍历(Python3)
  • 【数据挖掘 | 数据预处理】缺失值处理 重复值处理 文本处理 确定不来看看?
  • 二叉树问题——前/中/后/层遍历(递归与栈)
  • Nor Flash和Nand Flash的区别——笔记
  • 7+共病思路。WGCNA+多机器学习+实验简单验证,易操作
  • 开发者看亚马逊云科技1024【文末有福利~】
  • 操作系统(Linux)外壳程序shell 、用户、权限
  • C文件操作
  • drawio特性
  • LLM-Embedder
  • xsync 集群远程同步脚本
  • 30秒get视频号视频如何下载,保存视频号视频到本地方法!
  • 优化改进YOLOv5算法:加入SPD-Conv模块,让小目标无处遁形——(超详细)