当前位置:网站首页>leetcode刷题:二叉树11(平衡二叉树)
leetcode刷题:二叉树11(平衡二叉树)
2022-07-05 19:52:00 【涛涛英语学不进去】
110.平衡二叉树
给定一个二叉树,判断它是否是高度平衡的二叉树。
本题中,一棵高度平衡二叉树定义为:一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
示例 1:
给定二叉树 [3,9,20,null,null,15,7]
返回 true 。
示例 2:
给定二叉树 [1,2,2,3,3,null,null,4,4]
返回 false 。
这题,,,,好难,对我来说。
答案好巧妙。
使用递归
相当于层层往上返回,当都是叶子结点时,树的高度为0 + 1 ,否则就比较树的左右子树高度,如果差值 > 1,则是非平衡二叉树,不然取左右子树最高树 + 根结点 高度 为当前树的高度。
package com.programmercarl.tree;
import com.programmercarl.util.GenerateTreeNode;
import java.util.ArrayDeque;
import java.util.Deque;
/** * @ClassName IsBalanced * @Descriotion TODO * @Author nitaotao * @Date 2022/7/4 11:21 * @Version 1.0 * https://leetcode.cn/problems/balanced-binary-tree/ * 110. 平衡二叉树 **/
public class IsBalanced {
/** * 递归三部曲 * 1. 明确递归函数的参数和返回值 * 参数:当前传入节点 * 返回值:以当前传入结点为根结点的树的高度 * 如果当前传入结点为根结点的二叉树不是平衡二叉树,返回 -1 * <p> * 2. 明确终止条件 * 遇到空节点终止,返回0,表示当前结点以此结点为根结点的树的高度为0 * <p> * 3. 明确单层递归的逻辑 * 如何判断左右子树不平衡? * 左右子树高度差 > 1 返回 -1 * 返回当前高度差 * * @param root * @return */
public boolean isBalanced(TreeNode root) {
return getHeight(root) != -1;
}
// 高度为-1则不是平衡二叉树
public int getHeight(TreeNode root) {
//空结点高度为0
if (root == null) {
return 0;
}
int leftHeight = getHeight(root.left);
if (leftHeight == -1) {
return - 1;
}
int rightHeight = getHeight(root.right);
if (rightHeight == -1) {
return -1;
}
//高度差 > 1 , 则不对称
if (Math.abs(leftHeight - rightHeight) > 1) {
return -1;
}
//如果左右子树为平衡二叉树,返回树的整体高度 + 1
// 整体高度为 当前最高子树的高度 + 根结点的高度
return Math.max(leftHeight, rightHeight) + 1;
}
}
边栏推荐
- 面试官:Redis中集合数据类型的内部实现方式是什么?
- Add data to excel small and medium-sized cases through poi
- Do you know several assertion methods commonly used by JMeter?
- Tasks in GStreamer
- [AI framework basic technology] automatic derivation mechanism (autograd)
- 信息/数据
- Worthy of being a boss, byte Daniel spent eight months on another masterpiece
- 随机数生成的四种方法|Random|Math|ThreadLocalRandom|SecurityRandom
- Based on vs2017 and cmake GUI configuration, zxing and opencv are used in win10 x64 environment, and simple detection of data matrix code is realized
- What does software testing do? What are the requirements for learning?
猜你喜欢
【obs】QString的UTF-8中文转换到blog打印 UTF-8 char*
司空见惯 - 英雄扫雷鼠
软件测试是干什么的?学习有啥要求?
[AI framework basic technology] automatic derivation mechanism (autograd)
城链科技数字化创新战略峰会圆满召开
力扣 729. 我的日程安排表 I
[OBS] qstring's UTF-8 Chinese conversion to blog printing UTF-8 char*
图嵌入Graph embedding学习笔记
PHP uses ueditor to upload pictures and add watermarks
Necessary skills for interview in large factories, 2022android will not die, I will not fall
随机推荐
不愧是大佬,字节大牛耗时八个月又一力作
Microwave radar induction module technology, real-time intelligent detection of human existence, static micro motion and static perception
Worthy of being a boss, byte Daniel spent eight months on another masterpiece
The binary string mode is displayed after the value with the field type of longtext in MySQL is exported
selenium 元素信息
Relationship between floating elements and parent and brother boxes
Force buckle 1200 Minimum absolute difference
随机数生成的四种方法|Random|Math|ThreadLocalRandom|SecurityRandom
id选择器和类选择器的区别
[FAQ] summary of common causes and solutions of Huawei account service error 907135701
通过POI追加数据到excel中小案例
No matter how busy you are, you can't forget safety
The city chain technology Digital Innovation Strategy Summit was successfully held
Four methods of random number generation | random | math | threadlocalrandom | securityrandom
acm入门day1
Base du réseau neuronal de convolution d'apprentissage profond (CNN)
C#应用程序界面开发基础——窗体控制(5)——分组类控件
全网最全的低代码/无代码平台盘点:简道云、伙伴云、明道云、轻流、速融云、集简云、Treelab、钉钉·宜搭、腾讯云·微搭、智能云·爱速搭、百数云
Let's talk about threadlocalinsecurerandom
Is it safe for Guosen Securities to open an account online?