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

【LeetCode】110. 平衡二叉树

110. 平衡二叉树(简单)

在这里插入图片描述
在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

思路

  • 对二叉树做先序遍历,从底至顶返回子树最大高度,若判定某子树不是平衡树则“剪枝”直接向上返回

  • 递归返回值

    1. 当节点 root 左、右子树的高度差 > 1:返回 -1,代表此子树不是平衡树;
    2. 否则返回以节点 root 为根节点的子树的最大高度,即节点 root 的左、右子树中最大高度加1 ,(max(left,right) +1)
  • 递归终止条件

    1. 当抵达叶子节点时,返回高度 0;
    2. 当左(右)子树高度 left/right == -1 时,代表此子树的左子树不是平衡树,因此直接返回 -1;
  • isBalanced(root)

    返回值: 若 helper(root) != 1 ,则说明此树平衡,返回 true ; 否则返回 false。

代码

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:bool isBalanced(TreeNode* root) {// -1 表示不平衡return helper(root) != -1;}// 计算高度int helper(TreeNode* root){if(root == nullptr) return 0;int left = helper(root->left), right = helper(root->right);// -1 表示不平衡if(left == -1 || right == -1 || abs(left-right)>1){return -1;}// 返回子树的高度return max(left, right) + 1;}
};

相关文章:

【LeetCode】110. 平衡二叉树

110. 平衡二叉树(简单) 思路 对二叉树做先序遍历,从底至顶返回子树最大高度,若判定某子树不是平衡树则“剪枝”直接向上返回。 递归返回值: 当节点 root 左、右子树的高度差 > 1:返回 -1,代…...

SQL视图、存储过程、触发器

一、视图 (一)介绍 视图(view)是一种虚拟存在的表。视图中的数据并不在数据库中实际存在,行和列数据来自定义视图的查询中使用的表,并且是在使用视图时动态生成的。 通俗的讲,视图只保存了查询的SQL逻辑&…...

DNS隧道穿透

介绍: DNS隧道,是隧道技术中的一种。当我们的HTTP、HTTPS这样的上层协议、正反向端口转发都失败的时候,可以尝试使用DNS隧道。DNS隧道很难防范,因为平时的业务也好,使用也罢,难免会用到DNS协议进行解析&am…...

1.2 Scala变量与数据类型

一、变量声明 (一)简单说明 Scala中变量的声明使用关键字val和var。val类似Java中的final变量,也就是常量,一旦初始化将不可修改;var类似Java中的非final变量,可以被多次赋值,多次修改。 val - …...

深入探讨软件测试的质量度量指标

本文的目的是介绍项目中使用到主要质量指标,这些质量指标可以分为以下三类: 质量保证过程指标生产事故管理指标度量质量文化指标 质量保证过程指标 质量保证指标可以通过测试覆盖率来度量功能和非功能测试的覆盖率,同时也可以根据测试发现…...

6.12作业

1、pinia和vuex的区别 1.pinia没有mutations,只有state,getters,actions 2.pinia分模块不需要modules (之前vuex分模块需要modules) 3.pinia体积更小(性能更好) 4.pinia可以直接修改state数据 2、Vue2和vue3的响应式原理分别是什么&#x…...

RabbitMQ集群部署之镜像模式

RabbitMQ集群的普通模式中,一旦创建队列的主机宕机,队列就会不可用。不具备高可用能力。如果要解决这个问题,必须使用官方提供的镜像集群方案。 官方文档地址:https://www.rabbitmq.com/ha.html 1.镜像模式的特征 默认情况下&a…...

【算法】Remove Zero Sum Consecutive Nodes from Linked List 从链表中删去总和值为零的连续节点

文章目录 Remove Zero Sum Consecutive Nodes from Linked List 从链表中删去总和值为零的连续节点问题描述:分析代码 Remove Zero Sum Consecutive Nodes from Linked List 从链表中删去总和值为零的连续节点 问题描述: 给你一个链表的头节点 head&am…...

音悦台项目测试报告

文章目录 项目背景项目功能测试计划与设计功能测试自动化测试 测试结果功能测试结果UI自动化测试结果 项目背景 现如今人们的生活压力大,容易使人疲惫,为了使得人们在闲暇之余可以听音乐放松,为此设计出一款轻量的听音乐网站,快速…...

数据库存储过程和函数

MySQL存储过程和存储函数 MySQL中提供存储过程(procedure)与存储函数(function)机制,我们先将其统称为存储程序,一般的SQL语句需要先编译然后执行,存储程序是一组为了完成特定功能的SQL语句集&…...

Spring依赖注入有哪些?各有什么优缺点?

文章目录 前言概述一、属性注入1.1 实例1.2 优点1.3 缺点 二、Setter注入2.1 实例2.2 优点2.3 缺点 三、 构造方法注入3.1 实例3.2 优点3.3 缺点 四、扩展 前言 IoC和DI是Spring中重要的两个概念,其中IoC指的是控制反转,DI(依赖注入)指的是IoC的具体实现…...

java八股文-并发篇

并发篇 1. 线程状态 要求 掌握 Java 线程六种状态掌握 Java 线程状态转换能理解五种状态与六种状态两种说法的区别 六种状态及转换 分别是 新建 当一个线程对象被创建,但还未调用 start 方法时处于新建状态此时未与操作系统底层线程关联 可运行 调用了 start …...

Elasticsearch8.6.0安装

Elasticsearch 8.5.0 安装 Elasticsearch 简介Elasticsearch 8.6.0 安装创建网络拉取镜像运行镜像设置密码修改kibana配置绑定ES代码绑定:手动绑定: 配置ik分词器扩展词词典停用词词典 Elasticsearch 简介 Elasticsearch(ES) 是一…...

Vue - 第五天 动态组件 插槽 自定义指令

动态组件& 插槽& 自定义指令 一、动态组件1.什么是动态组件2.如何实现动态组件渲染3.使用 keep-alive 保持状态4. keep-alive 对应的生命周期函数5. keep-alive 的 include 属性6.动态展示左右组件7.例子 二、插槽1.什么是插槽2.体验插槽的基础用法2.1 没有预留插槽的内…...

如何开展web自动化测试

Web 自动化是指使用测试脚本在 Web 上自动执行任务。它包括填写表单、导航网页、单击链接或按钮以及从网站中提取数据等任务。 它可用于各种目的,例如自动输入数据或测试网站的功能。有几种工具和编程语言可用于自动化网络上的任务,包括Selenium&#x…...

【博学谷学习记录】超强总结,用心分享 | 架构师 Maven学习总结

文章目录 Maven基本1.什么是Maven2.为什么用Maven?(1)jar 包的规模(2) jar 包的来源(3)jar 包之间的依赖关系 3.Maven目录结构4.maven仓库配置 Pom层次Pom文件简介Super POM 依赖管理1 依赖传递2 传递性依…...

PPT里文字太多如何排版-一口气教你7种布局瞬间让PPT高大上起来

简介 这是我们学PPT处于初级到中级进化阶段常做的一件事,就是拿了这种纯文字类版面来做布局。而且这种文字都是政企类的、相当苦涩难懂、无法创意。 因此我们会要求使用7种排版来优化这个版面。这和达芳奇画鸡蛋很像,这样的练习需要坚持一段时间,就是拿了纯文字来beautifu…...

Whistle(基于 Node 实现的跨平台抓包调试工具)的使用

Whistle(基于 Node 实现的跨平台抓包调试工具)的使用 基于Node实现的跨平台抓包调试工具 可以劫持网络请求,并进行请求和响应的修改,来提高我们的开发调试效率 1.一键安装(装包/证书) npm i -g whistle && w2 start --init 证书的问题 安装…...

数学模型:Python实现非线性规划

上篇文章:整数规划 文章摘要:非线性规划的Python实现。 参考书籍:数学建模算法与应用(第3版)司守奎 孙玺菁。 PS:只涉及了具体实现并不涉及底层理论。学习底层理论以及底层理论实现:可以参考1.最优化模型与算法——基于…...

Docker网路模型(四)使用 bridge 网络

使用 bridge 网络 在计算机网络中,一个 bridge(网桥)是一个链路层设备,负责在不同的网段之间转发信息。 bridge 可以是真实的硬件设备也可以是由宿主机底层提供的软件模拟设备。 在 Docker 中,bridge 网络使用了软件…...

深入剖析AI大模型:大模型时代的 Prompt 工程全解析

今天聊的内容,我认为是AI开发里面非常重要的内容。它在AI开发里无处不在,当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗",或者让翻译模型 "将这段合同翻译成商务日语" 时,输入的这句话就是 Prompt。…...

《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》

引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...

理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端

🌟 什么是 MCP? 模型控制协议 (MCP) 是一种创新的协议,旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议,它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...

LeetCode - 394. 字符串解码

题目 394. 字符串解码 - 力扣(LeetCode) 思路 使用两个栈:一个存储重复次数,一个存储字符串 遍历输入字符串: 数字处理:遇到数字时,累积计算重复次数左括号处理:保存当前状态&a…...

pam_env.so模块配置解析

在PAM(Pluggable Authentication Modules)配置中, /etc/pam.d/su 文件相关配置含义如下: 配置解析 auth required pam_env.so1. 字段分解 字段值说明模块类型auth认证类模块,负责验证用户身份&am…...

Objective-C常用命名规范总结

【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名(Class Name)2.协议名(Protocol Name)3.方法名(Method Name)4.属性名(Property Name)5.局部变量/实例变量(Local / Instance Variables&…...

SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现

摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序,以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务,提供稳定高效的数据处理与业务逻辑支持;利用 uniapp 实现跨平台前…...

JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作

一、上下文切换 即使单核CPU也可以进行多线程执行代码,CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短,所以CPU会不断地切换线程执行,从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...

Spring数据访问模块设计

前面我们已经完成了IoC和web模块的设计,聪明的码友立马就知道了,该到数据访问模块了,要不就这俩玩个6啊,查库势在必行,至此,它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据(数据库、No…...

在QWebEngineView上实现鼠标、触摸等事件捕获的解决方案

这个问题我看其他博主也写了,要么要会员、要么写的乱七八糟。这里我整理一下,把问题说清楚并且给出代码,拿去用就行,照着葫芦画瓢。 问题 在继承QWebEngineView后,重写mousePressEvent或event函数无法捕获鼠标按下事…...