Leetcode110_平衡二叉树

1.leetcode原题链接:. - 力扣(LeetCode)

2.题目描述

给定一个二叉树,判断它是否是 

平衡二叉树

  

示例 1:

输入:root = [3,9,20,null,null,15,7]
输出:true

示例 2:

输入:root = [1,2,2,3,3,null,null,4,4]
输出:false

示例 3:

输入:root = []
输出:true

提示:

  • 树中的节点数在范围 [0, 5000] 内
  • -104 <= Node.val <= 104

3.实现方法

方法一:自顶向下

从根节点开始,自顶向下递归地判断左右子树是否平衡,先分别计算当前节点左右子树的高度,如果高度差不超过1,那么再递归地分别判断左右子树。

class Solution {
    public boolean isBalanced(TreeNode root) {
        if ( root == null ) return true;
        return Math.abs( height(root.left) - height(root.right) ) <= 1
                && isBalanced(root.left)
                && isBalanced(root.right);
    }
    // 定义一个height方法,用于计算树的高度
    public int height(TreeNode root){
        if ( root == null ) return 0;
        return Math.max( height(root.left), height(root.right) ) + 1;
    }
}

方法二:自底向上

   自底向上地遍历节点进行判断。计算每个节点的高度时,需要递归地处理左右子树;所以可以先判断左右子树是否平衡,计算出左右子树的高度,再判断当前节点是否平衡。这样,计算高度的方法height,对于每个节点就只调用一次了。

class Solution {
    public boolean isBalanced(TreeNode root) {
    if ( root == null ) return true;
    int leftHeight = balancedHeight(root.left);
    int rightHeight = balancedHeight(root.right);
    return leftHeight != -1 && rightHeight != -1 && Math.abs( leftHeight - rightHeight ) <= 1;
}
  // 定义一个height方法
  public int balancedHeight(TreeNode root){
    if ( root == null ) return 0;
    int leftHeight = balancedHeight(root.left);
    int rightHeight = balancedHeight(root.right);
    // 如果子树不平衡,直接返回-1
    if ( leftHeight == -1 || rightHeight == -1 || Math.abs( leftHeight - rightHeight ) > 1)
        return -1;
    // 如果平衡,高度就是左右子树高度最大值,再加1
    return Math.max( leftHeight, rightHeight ) + 1;
 }
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/535807.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

OJ刷题日记:1、双指针(1)

目录 1、283.移动零 2、1089.复写零 3、202.快乐数 1、283.移动零 题目&#xff1a; 给定一个数组 nums&#xff0c;编写一个函数将所有 0 移动到数组的末尾&#xff0c;同时保持非零元素的相对顺序。 请注意 &#xff0c;必须在不复制数组的情况下原地对数组进行操作。 …

牛客小白月赛90(A,B,C,D,E,F)

比赛链接 官方题解&#xff08;视频&#xff09; 这场偏思维&#xff0c;感觉好像没啥算法。E需要动态维护前 k k k 小&#xff0c;F是个离散化加dp&#xff0c;状态和递推方程比较 非常规&#xff0c;建议还是看一下涨涨姿势。 A 小A的文化节 思路&#xff1a; 签到 cod…

我国量子信息科技创新发展面临的挑战及建议——基于中美对比视角的分析

2024年2月&#xff0c;中国科学技术发展战略院慕慧娟博士、丁明磊研究员及光子盒顾成建一起在《科技管理研究》上发表文章——《我国量子信息科技创新发展面临的挑战及建议&#xff1a;基于中美对比视角的分析》。 在此&#xff0c;我们整理并发布这篇文章&#xff0c;欢迎感兴…

springCloudAlibaba集成sentinel实战(超详细)

一、Sentinel介绍 1. 什么是Sentinel Sentinel是阿里开源的项目&#xff0c;提供了流量控制、熔断降级、系统负载保护等多个维度来保障服务之间的稳定性。 分布式系统的流量防卫兵&#xff1a; 随着微服务的普及&#xff0c;服务调用的稳定性变得越来越重要。Sentinel以“流…

实现创建线程的五种写法

创建线程的五种写法 1、通过继承Thread类并实现run方法创建一个线程package 创建线程;2、通过实现Runnable接口&#xff0c;并实现run方法的方法创建一个线程3、通过Thread匿名内部类创建一个线程4、通过Runnable匿名内部类创建一个线程5、通过Lambda表达式的方式创建一个线程 …

airtest-ios真机搭建实践

首先阅读4 ios connection - Airtest Project Docs 在Windows环境下搭建Airtest对iOS真机进行自动化测试的过程相对复杂&#xff0c;因为iOS的自动化测试通常需要依赖Mac OS系统&#xff0c;但理论上借助一些工具和服务&#xff0c;Windows用户也可以间接完成部分工作。下面是…

IP SSL证书免费申请教程(给IP地址开启https)

首先IP地址申请的前提&#xff1a;80端口有打开&#xff0c;或者可以短暂的打开10分钟左右等验证完IP管理权再关掉。 一&#xff1a;打开JoySSL官网选择IP地址证书并下单加入购物车&#xff0c;之后结账后就会跳转到证书申请界面。 二&#xff1a;填写需要申请证书的IP信息 三&…

【RV1106的ISP使用记录之一】基础环境搭建

公司缺少ISP工程师&#xff0c;做为图像算法工程师的我这就不就给顶上来了么&#xff0c;也没给发两份工资&#xff0c;唉~ 先写个标题&#xff0c;占一个新坑&#xff0c;记录RK平台的传统ISP工作。 一、基础环境的硬件包括三部分&#xff1a; 1、相机环境&#xff0c;用于采…

Python 网络爬虫技巧分享:优化 Selenium 滚动加载网易新闻策略

简介 网络爬虫在数据采集和信息获取方面发挥着重要作用&#xff0c;而滚动加载则是许多网站常用的页面加载方式之一。针对网易新闻这样采用滚动加载的网站&#xff0c;如何优化爬虫策略以提高效率和准确性是一个关键问题。本文将分享如何利用 Python 中的 Selenium 库优化滚动…

利用爬虫技术实现自动化数据分析

目录 前言 一、爬虫技术概述 二、自动化数据分析的步骤 1. 确定数据需求 2. 网页分析和定位 3. 编写爬虫程序 4. 数据存储和处理 5. 数据分析和可视化 三、示例代码 总结 前言 在信息时代&#xff0c;数据已成为重要的资源之一&#xff0c;并且随着互联网的发展&…

计算机网络——交换机和路由器

目录 前言 引言 交换机是用来做什么的&#xff1f; 与路由器有什么区别&#xff1f; 网关 子网掩码 网关、路由 前言 本博客是博主用于复习计算机网络的博客&#xff0c;如果疏忽出现错误&#xff0c;还望各位指正。 这篇博客是在B站掌芝士zzs这个UP主的视频的总结&am…

flutter跑通腾讯云直播Demo

运行示例 前提条件 要求java jdk 11版本 并且配置到了环境变量 重要 要求flutter 版本 2.8.0 并且配置到了环境变量 重要 要求dart-sdk版本2.15 并且配置到了环境变量 重要 您已 注册腾讯云 账号&#xff0c;并完成 实名认证。 申请 SDKAPPID 和 SECRETKEY 登录实时音视频控…

全栈开发医疗小程序 SpringBoot2.X + Vue + UniAPP 带源码

看到好多坛友都在求SpringBoot2.X Vue UniAPP&#xff0c;全栈开发医疗小程序 – 带源码课件&#xff0c;我看了一下&#xff0c;要么链接过期&#xff0c;要么课件有压缩密码。特意整理了一份分享给大家&#xff0c;个人认为还是比较全面的。希望对大家有所帮助&#xff01;…

FFmpeg: 简易ijkplayer播放器实现--04消息队列设计

文章目录 播放器状态转换图播放器状态对应的消息&#xff1a; 消息对象消息队列消息队列api插入消息获取消息初始化消息插入消息加锁初始化消息设置消息参数消息队列初始化清空消息销毁消息启动消息队列终止消息队列删除消息 消息队列&#xff0c;用于发送&#xff0c;设置播放…

探探各个微前端框架

本文作者为 360 奇舞团前端开发工程师 微前端架构是为了在解决单体应用在一个相对长的时间跨度下&#xff0c;由于参与的人员、团队的增多、变迁&#xff0c;从一个普通应用演变成一个巨石应用(Frontend Monolith)后&#xff0c;随之而来的应用不可维护的问题。这类问题在企业级…

全新华为MateBook X Pro发布,将Ultra9放入980g超轻薄机身

2024年4月11日&#xff0c;在华为鸿蒙生态春季沟通会上全新的华为MateBook X Pro正式发布。该机以美学设计、创新科技以及智慧体验&#xff0c;追求重新定义Pro、重新定义旗舰&#xff0c;将颠覆消费者对传统轻薄本的认知。 华为MateBook X Pro追求极致轻薄与强大性能的完美结合…

怎样将PDF转成PPT,有免费的工具吗?

PDF转换为PPT的需求在现代办公和学习中越来越常见。很多人可能遇到过需要将PDF文件中的内容转移到PPT中以方便编辑和展示的情况。幸运的是&#xff0c;现在市面上有许多工具可以帮助我们实现这一目标&#xff0c;而且其中不乏一些免费的选项。本文将详细介绍如何使用这些免费工…

linux学习:栈

目录 顺序栈 结构 初始化一个空顺序栈 压栈 出栈 例子 十进制转八进制 链式栈 管理结构体的定义 初始化 压栈 出栈 顺序栈 顺序栈的实现&#xff0c;主要就是定义一块连续的内存来存放这些栈元素&#xff0c;同时为了方便管理&#xff0c; 再定义一个整数变量来代表…

计算机基础知识-第9章-存储的本质(2)——硬盘和文件系统基础知识

一、机械硬盘的原理 概括来说&#xff0c;硬盘的工作原理是利用特定的磁粒子的极性来记录数据。磁头在读取数据时&#xff0c;将磁力子的不同极性转换成不同的电脉冲信号&#xff0c;再利用数据转换器将这些原始信号变成电脑可以使用的数据&#xff0c;写的操作正好与此相反。…

前端docker jenkins nginx CI/CD持续集成持续部署-实战

最近用go react ts开发了一个todolist后端基本开发完了,前端采用CI/CD方式去部署。 步骤总结 先安装docker 和 docker-compose。安装jenkins镜像,跑容器的时候要配好数据卷。配置gitee或github(我这里使用gitee)在服务器上一定要创建好dokcer的数据卷,以便持久保存jenkin…