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

【算法】平衡二叉树

难度:简单

题目

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

示例:

示例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

解题思路:

暴力解判断一棵二叉树是否是平衡二叉树,我们需要理解“平衡”的定义:对于树中的任意节点,它的左子树和右子树的高度差不超过1。这个问题可以通过自底向上递归的方式来解决,每个递归函数返回两个值:当前子树是否平衡以及该子树的高度。

  1. 定义递归函数:编写一个递归函数,该函数接收一个树节点作为参数。这个函数需要返回两个值:
    ○ 一个布尔值,表示以该节点为根的子树是否平衡。
    ○ 一个整数,表示以该节点为根的子树的高度。
  2. 基本情况
    ○ 如果节点为空,可以直接返回“平衡”状态(true)以及高度0,因为空树被认为是平衡的。
  3. 递归计算
    ○ 对当前节点的左子树进行递归调用,得到左子树是否平衡及高度。
    ○ 对当前节点的右子树进行递归调用,得到右子树是否平衡及高度。
  4. 判断并返回
    ○ 根据左、右子树的平衡状态和高度,判断当前节点的子树是否平衡:
    ■ 如果左、右子树都平衡且它们的高度差不超过1,则当前子树平衡。
    ■ 否则,当前子树不平衡。
    ○ 计算当前子树的高度,即左右子树高度中的较大者加1。
  5. 主函数调用:从根节点开始调用递归函数,仅关心返回的平衡状态,忽略高度信息。
JavaScript实现:
// 定义二叉树节点
class TreeNode {constructor(val, left = null, right = null) {this.val = val;this.left = left;this.right = right;}
}// 判断是否平衡的递归函数
function isBalancedHelper(node) {if (!node) return [true, 0]; // 空树,高度为0,平衡const [leftBalanced, leftHeight] = isBalancedHelper(node.left);const [rightBalanced, rightHeight] = isBalancedHelper(node.right);// 当前节点是否平衡的判断依据const balanced = leftBalanced && rightBalanced && Math.abs(leftHeight - rightHeight) <= 1;// 当前子树的高度const height = Math.max(leftHeight, rightHeight) + 1;return [balanced, height];
}// 主函数
function isBalanced(root) {return isBalancedHelper(root)[0]; // 只关心是否平衡的结果
}// 示例
//const root = new TreeNode(1,
//     new TreeNode(2,
//         new TreeNode(3),
//         new TreeNode(4)),
//     new TreeNode(2));
// console.log(isBalanced(root)); // 输出: false,因为右子树的左子树高度为2,导致不平衡

这段代码首先定义了二叉树节点的构造函数TreeNode,然后定义了辅助递归函数isBalancedHelper来判断子树的平衡状态和计算高度,最后是主函数isBalanced来调用辅助函数并返回是否平衡的结果。

相关文章:

【算法】平衡二叉树

难度&#xff1a;简单 题目 给定一个二叉树&#xff0c;判断它是否是 平衡二叉树 示例&#xff1a; 示例1&#xff1a; 输入&#xff1a;root [3,9,20,null,null,15,7] 输出&#xff1a;true 示例2&#xff1a; 输入&#xff1a;root [1,2,2,3,3,null,null,4,4] 输出&…...

五、 计算机网络(考点篇)

1 网络概述和模型 计算机网络是计算机技术与通信技术相结合的产物&#xff0c;它实现了远程通信、远程信息处理和资源共享。计算机网络的功能&#xff1a;数据通信、资源共享、管理集中化、实现分布式处理、负载均衡。 网络性能指标&#xff1a;速率、带宽(频带宽度或传送线路…...

如何解决数据分析问题:IPython与Pandas结合

如何解决数据分析问题&#xff1a;IPython与Pandas结合 数据分析是现代科学研究、商业决策和技术开发中的一个重要环节。IPython和Pandas是两个强大的工具&#xff0c;它们可以大大简化和加速数据分析的过程。本文将为初学者详细介绍如何结合使用IPython和Pandas来解决数据分析…...

如何在 Microsoft Edge 上使用开发人员工具

Microsoft Edge 提供了一套强大的开发人员工具&#xff0c;可帮助 Web 开发人员检查、调试和优化他们的网站或 Web 应用程序。 无论您是经验丰富的 Web 开发人员还是刚刚起步&#xff0c;了解如何有效地使用这些工具都可以对开发过程产生重大影响。 在本文中&#xff0c;我们…...

《Linux系统编程篇》认识在linux上的文件 ——基础篇

前言 Linux系统编程的文件操作如同掌握了一把魔法钥匙&#xff0c;打开了无尽可能性的大门。在这个世界中&#xff0c;你需要了解文件描述符、文件权限、文件路径等基础知识&#xff0c;就像探险家需要了解地图和指南针一样。而了解这些基础知识&#xff0c;就像学会了魔法咒语…...

Qt:22.鼠标相关事件(实例演示——鼠标进入/离开某控件的事件、鼠标按下事件、鼠标释放事件、鼠标双击事件)

目录 1.实例演示——鼠标进入/离开某控件的事件&#xff1a; 2.鼠标按下事件&#xff1a; 3.鼠标释放事件&#xff1a; 4.鼠标双击事件&#xff1a; 1.实例演示——鼠标进入/离开某控件的事件&#xff1a; 首先创建一个C类文件 Label&#xff0c;填写好要继承的父类 QLabe…...

笔记 4 :linux 0.11 中继续分析 0 号进程创建一号进程的 fork () 函数

&#xff08;27&#xff09;本条目开始&#xff0c; 开始分析 copy_process () 函数&#xff0c;其又会调用别的函数&#xff0c;故先分析别的函数。 get_free_page &#xff08;&#xff09; &#xff1b; 先 介绍汇编指令 scasb &#xff1a; 以及 指令 sstosd &#xff1a;…...

Vue3 引入Vanta.js使用

能搜到这篇文章 想必一定看过demo效果图了吧 示例 Vanta.js - Animated 3D Backgrounds For Your Website (vantajs.com) 1. 引入 在根目录 index.html中引入依赖 <script src"https://cdnjs.cloudflare.com/ajax/libs/three.js/r134/three.min.js"></sc…...

LeetCode --- 134双周赛

题目 3206. 交替组 I 3207. 与敌人战斗后的最大分数 3208. 交替组 II 3209. 子数组按位与值为 K 的数目 一、交替组 I & II 题目中问环形数组中交替组的长度为3的子数组个数&#xff0c;主要的问题在于它是环形的&#xff0c;我们要考虑首尾相接的情况&#xff0c;如何…...

快速读出linux 内核中全局变量

查问题时发现全局变量能读出来会提高效率&#xff0c;于是考虑从怎么读出内核态的全局变量&#xff0c;脚本如下 f open("/proc/kcore", rb) f.seek(4) # skip magic assert f.read(1) b\x02 # 64 位def read_number(bytes):return int.from_bytes(bytes, little,…...

postman录制设置

一、前言&#xff1a; ​ postman是一个很好接口调试或是测试工具&#xff0c;简单方便&#xff0c;不需要很复杂的流程与技术&#xff0c;并且也具备录制条件。对于接口不了解&#xff0c;没有明确对应的说明&#xff0c;但又想通过接口进行一些测试使用其录制是一个不错的办…...

redis消息队列

redis 的list类型实现消息队列&#xff1a; list结构实现的优缺点&#xff1a; 2、pubsub模式&#xff08;消息发布订阅&#xff09;实现消息队列 pubsub的优缺点&#xff1a; 命令行实现&#xff1a; pub:第一次发送有两个接收&#xff0c;第二个只有一个接收 sub接收&#x…...

Linux vim的使用(一键安装则好用的插件_forcpp),gcc的常见编译链接操作

vim 在Linux系统上vim是个功能还比较完善的软件。但是没装插件的vim用着还是挺难受的&#xff0c;所以我们直接上一款插件。 我们只需要在Linux上执行这个命令就能安装(bite提供的) curl -sLf https://gitee.com/HGtz2222/VimForCpp/raw/master/install.sh -o ./install.sh …...

css基础(1)

CSS CCS Syntax CSS 规则由选择器和声明块组成。 CSS选择器 CSS选择器用于查找想要设置样式的HTML元素 一般选择器分为五类 Simple selectors (select elements based on name, id, class) 简单选择器&#xff08;根据名称、id、类选择元素&#xff09; //页面上的所有 …...

高并发线程池设计Nginx线程池源码剖析

为什么我们需要线程池?Why? 省流&#xff1a; 为了解决: 1.访问磁盘速度慢 2.等待设备工作 3..... 我们使用多线程技术&#xff0c;在IO繁忙的时候优先处理别的任务 为了解决多线程的缺陷: 1.创建、销毁线程时间消耗大 2.创建线程太多使系统资源不足或者线程频繁切换…...

SEO:6个避免被搜索引擎惩罚的策略-华媒舍

在当今数字时代&#xff0c;搜索引擎成为了绝大多数人获取信息和产品的首选工具。为了在搜索结果中获得良好的排名&#xff0c;许多网站采用了各种优化策略。有些策略可能会适得其反&#xff0c;引发搜索引擎的惩罚。以下是彭博社发稿推广的6个避免被搜索引擎惩罚的策略。 1. 内…...

STM32之六:SysTick系统滴答定时器

目录 1. SysTick简介 2. 时钟来源 3. SysTick寄存器 3.1 CTRL—SysTick控制及状态寄存器 3.2 RELOAD—SysTick重装载数值寄存器 3.3 CURRENT—SysTick当前数值寄存器 4. systick系统定时器配置 5. 延时函数实现 5.1 延时函数编写步骤 5.2 微秒级延时函数delay_us 5.…...

全栈物联网项目:结合 C/C++、Python、Node.js 和 React 开发智能温控系统(附代码示例)

1. 项目概述 本文详细介绍了一个基于STM32微控制器和AWS IoT云平台的智能温控器项目。该项目旨在实现远程温度监控和控制,具有以下主要特点: 使用STM32F103微控制器作为主控芯片,负责数据采集、处理和控制逻辑采用DHT22数字温湿度传感器,精确采集环境温湿度数据通过ESP8266 W…...

WPF学习(3) -- 控件模板

一、操作过程 二、代码 <Window x:Class"学习.MainWindow"xmlns"http://schemas.microsoft.com/winfx/2006/xaml/presentation"xmlns:x"http://schemas.microsoft.com/winfx/2006/xaml"xmlns:d"http://schemas.microsoft.com/expressio…...

Netty Websocket SpringBoot Starter

netty websocket starter Quick Start Demo 项目 添加依赖 <!--添加源--> <repository><id>github</id><url>https://maven.pkg.github.com</url><snapshots><enabled>true</enabled></snapshots> </reposit…...

Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)

目录 1.TCP的连接管理机制&#xff08;1&#xff09;三次握手①握手过程②对握手过程的理解 &#xff08;2&#xff09;四次挥手&#xff08;3&#xff09;握手和挥手的触发&#xff08;4&#xff09;状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...

Neo4j 集群管理:原理、技术与最佳实践深度解析

Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...

C++中string流知识详解和示例

一、概览与类体系 C 提供三种基于内存字符串的流&#xff0c;定义在 <sstream> 中&#xff1a; std::istringstream&#xff1a;输入流&#xff0c;从已有字符串中读取并解析。std::ostringstream&#xff1a;输出流&#xff0c;向内部缓冲区写入内容&#xff0c;最终取…...

Matlab | matlab常用命令总结

常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...

三体问题详解

从物理学角度&#xff0c;三体问题之所以不稳定&#xff0c;是因为三个天体在万有引力作用下相互作用&#xff0c;形成一个非线性耦合系统。我们可以从牛顿经典力学出发&#xff0c;列出具体的运动方程&#xff0c;并说明为何这个系统本质上是混沌的&#xff0c;无法得到一般解…...

基于matlab策略迭代和值迭代法的动态规划

经典的基于策略迭代和值迭代法的动态规划matlab代码&#xff0c;实现机器人的最优运输 Dynamic-Programming-master/Environment.pdf , 104724 Dynamic-Programming-master/README.md , 506 Dynamic-Programming-master/generalizedPolicyIteration.m , 1970 Dynamic-Programm…...

Selenium常用函数介绍

目录 一&#xff0c;元素定位 1.1 cssSeector 1.2 xpath 二&#xff0c;操作测试对象 三&#xff0c;窗口 3.1 案例 3.2 窗口切换 3.3 窗口大小 3.4 屏幕截图 3.5 关闭窗口 四&#xff0c;弹窗 五&#xff0c;等待 六&#xff0c;导航 七&#xff0c;文件上传 …...

Python+ZeroMQ实战:智能车辆状态监控与模拟模式自动切换

目录 关键点 技术实现1 技术实现2 摘要&#xff1a; 本文将介绍如何利用Python和ZeroMQ消息队列构建一个智能车辆状态监控系统。系统能够根据时间策略自动切换驾驶模式&#xff08;自动驾驶、人工驾驶、远程驾驶、主动安全&#xff09;&#xff0c;并通过实时消息推送更新车…...

日常一水C

多态 言简意赅&#xff1a;就是一个对象面对同一事件时做出的不同反应 而之前的继承中说过&#xff0c;当子类和父类的函数名相同时&#xff0c;会隐藏父类的同名函数转而调用子类的同名函数&#xff0c;如果要调用父类的同名函数&#xff0c;那么就需要对父类进行引用&#…...

Chrome 浏览器前端与客户端双向通信实战

Chrome 前端&#xff08;即页面 JS / Web UI&#xff09;与客户端&#xff08;C 后端&#xff09;的交互机制&#xff0c;是 Chromium 架构中非常核心的一环。下面我将按常见场景&#xff0c;从通道、流程、技术栈几个角度做一套完整的分析&#xff0c;特别适合你这种在分析和改…...