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

力扣刷题-二叉树-二叉树的高度与深度

二叉树最大深度

给定一个二叉树 root ,返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
示例 1:
image.png
输入:root = [3,9,20,null,null,15,7]
输出:3

递归法

本题可以使用前序(中左右),也可以使用后序遍历(左右中),使用前序求的就是深度,使用后序求的是高度。
二叉树节点的深度:指从根节点到该节点的最长简单路径边的条数或者节点数(取决于深度从0开始还是从1开始)
二叉树节点的高度:指从该节点到叶子节点的最长简单路径边的条数或者节点数(取决于高度从0开始还是从1开始)
根节点的高度就是二叉树的最大深度
,所以本题中我们通过
后序
求的根节点高度来求的二叉树最大深度。
这一点其实是很多同学没有想清楚的,很多题解同样没有讲清楚。
image.png
体现后序遍历的过程!!!使用前序的话要复杂的多
递归第一点:参数就是传入树的根节点,返回就返回这棵树的深度,所以返回值为int类型。
递归第二点:如果为空节点的话,就返回0,表示高度为0。
递归第三点:
**先求它的左子树的深度,再求右子树的深度,最后取左右深度最大的数值 再+1 **(加1是因为算上当前中间节点)就是目前节点为根节点的树的深度。(也就是高度)

class solution:def maxdepth(self, root: treenode) -> int:return self.getdepth(root)def getdepth(self, node):if not node:return 0leftdepth = self.getdepth(node.left) # 左rightdepth = self.getdepth(node.right) # 右depth = max(leftdepth, rightdepth) + 1 # 中return depth

精简版:

class solution:def maxdepth(self, root: treenode) -> int:if not root:return 0return 1 + max(self.maxdepth(root.left), self.maxdepth(root.right))

层次遍历

from collections import dequeclass TreeNode(object):def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightclass Solution(object):def maxDepth(self, root):""":type root: TreeNode:rtype: int"""if not root:return 0result = []queue = deque([root])while queue:level_result = []for _ in range(len(queue)):cur = queue.popleft()level_result.append(cur.val)if cur.left:queue.append(cur.left)if cur.right:queue.append(cur.right)result.append(level_result)return len(result) # 里面多少嵌套列表 即为最大深度

参考:
https://www.programmercarl.com/0104.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%9C%80%E5%A4%A7%E6%B7%B1%E5%BA%A6.html

相关文章:

力扣刷题-二叉树-二叉树的高度与深度

二叉树最大深度 给定一个二叉树 root ,返回其最大深度。 二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。 示例 1: 输入:root [3,9,20,null,null,15,7] 输出:3 递归法 本题可以使用前序(中左…...

Vue3新增加的css语法糖

一、deep <template><div class""><el-input /> </div> </template> <style scoped> /* 样式穿透 */ :deep input {background: red; } </style> 二、slotted 子组件修改插槽里面的样式 <template><div clas…...

Windows安装Vmware 虚拟机

目录 一、Vmware 虚拟机介绍 二、Vmware 虚拟机的三种网络模式 2.1桥接模式 2.2仅主机模式 2.3NAT 网络地址转换模式 三、Vmware 虚拟机的安装 一、Vmware 虚拟机介绍 VMware Workstation Pro 是一款可以在个人电脑的操作系统上创建一个完全与主机操作系统隔离的 虚拟机&…...

uniapp地图手动控制地图scale

前言 首次使用uniapp开发地图过程中&#xff0c;发现uniapp地图居然没有提供手动控制地图scale的方法&#xff0c;这个也着实没有想到&#xff0c;查了半天资料&#xff0c;也终于找到一个方法能够比较好的控制scale&#xff0c;做个记录。 代码 要定义一个地图map&#xff…...

Kotlin学习之函数

原文链接 Understanding Kotlin Functions 函数对于编程语言来说是极其重要的一个组成部分&#xff0c;函数可以视为是程序的执行&#xff0c;是真正活的代码&#xff0c;为啥呢&#xff1f;因为运行的时候你必须要执行一个函数&#xff0c;一般从主函数入口&#xff0c;开始一…...

若依启动步骤

1.创建数据库 2.启动redis 3.改后端的数据库连接配置 4.配置redis redis的地址&#xff1a;cmd中ipconfig命令查看 6.启动后端&#xff1a;如下 7.启动前端ruoyi-ui中 先运行npm install&#xff0c;再npm run dev。项目就启动成功了。 用户名&#xff1a;admin 密码&#x…...

qt-C++笔记之两个窗口ui的交互

qt-C笔记之两个窗口ui的交互 code review! 文章目录 qt-C笔记之两个窗口ui的交互0.运行1.文件结构2.先创建widget项目&#xff0c;搞一个窗口ui出来3.项目添加第二个widget窗口出来4.补充代码4.1.qt_widget_interaction.pro4.2.main.cpp4.3.widget.h4.4.widget.cpp4.5.second…...

Redis-核心数据结构

五种数据结构 String结构 String结构应用场景 Hash结构 Hash结构应用场景 List结构 List结构应用场景 Set结构 Set结构应用场景 ZSet有序结构 ZSet有序结构应用场景...

设计模式—结构型模式之外观模式(门面模式)

设计模式—结构型模式之外观模式&#xff08;门面模式&#xff09; 外观&#xff08;Facade&#xff09;模式又叫作门面模式&#xff0c;是一种通过为多个复杂的子系统提供一个一致的接口&#xff0c;而使这些子系统更加容易被访问的模式。 例子 我们的电脑会有很多 组件&am…...

CentOS Stream 9-使用 systemd 管理自己程序时自定义日志路径

systemd 文件 [rootnode1 ~]# cat /etc/systemd/system/spms-wvp.service [Unit] DescriptionWVP service [Service] # 关键配置部分,注意这里的 spms-wvp &#xff0c;后面需要用 SyslogIdentifierspms-wvp StandardOutputsyslog StandardErrorsyslog Typesimple Environment…...

动态页面调研及设计方案

文章目录 vue2 动态表单、动态页面调研一、form-generator二、ng-form-element三、Variant Form四、form-create vue2 动态表单、动态页面调研 一、form-generator 预览&#xff1a;https://mrhj.gitee.io/form-generator/#/ Vue2 Element UI支持拖拽生成表单不支持其他组件…...

鸿蒙4.0开发笔记之DevEco Studio之配置代码片段快速生成(三)

一、作用 配置代码片段可以让我们在Deveco Studio中进行开发时快速调取常用的代码块、字符串或者某段具有特殊含义的文字。其实现方式类似于调用定义好变量&#xff0c;然而这个变量是存在于Deveco Studio中的&#xff0c;并不会占用项目的资源。 二、配置代码段的方法 1、打…...

HarmonyOS真机调试报错:INSTALL_PARSE_FAILED_USESDK_ERROR处理

文章目录 1、 新建应用时选择与自己真机匹配的sdk版本2、 根据报错提示连接打开处理方案3、查询真机版本对应的**compileSdkVersion** 和 **compatibleSdkVersion** 提示3.1版本之后和3.1版本之前的不同命令&#xff08;此处为3.0版本&#xff09;4、根据查询修改参数5、连接成…...

webSocket基于面向对象二次封装

今天不睡,熬夜赶了个WebSocket 二次封装,也对这几天文章摸鱼感到抱歉,所以我出了一个注释非常非常全的代码 思路如下 首先&#xff0c;需要通过调用connect方法来建立WebSocket连接。当连接成功时&#xff0c;会调用我提供的回调函数&#xff0c;并将连接成功的消息帧作为参数…...

【Web】PHP反序列化的一些trick

目录 ①__wakeup绕过 ②加号绕过正则匹配 ③引用绕过相等 ④16进制绕过关键词过滤 ⑤Exception绕过 ⑥字符串逃逸 要中期考试乐(悲) ①__wakeup绕过 反序列化字符串中表示属性数量的值 大于 大括号内实际属性的数量时&#xff0c;wakeup方法会被绕过 &#xff08;php5-p…...

【测试功能篇 01】Jmeter 压测接口最大并发量、吞吐量、TPS

压力测试&#xff0c;我们针对比较关键的接口&#xff0c;可以进行相应的压力测试&#xff0c;主要还是测试看看接口能抗住多少的请求数&#xff0c;TPS稳定在多少&#xff0c;也就是吞吐量多少 安装 Jmeter的安装很简单&#xff0c;官网下载地址 http://jmeter.apache.org/ &…...

代码随想录算法训练营第四十九天| 123.买卖股票的最佳时机III 188.买卖股票的最佳时机IV

文档讲解&#xff1a;代码随想录 视频讲解&#xff1a;代码随想录B站账号 状态&#xff1a;看了视频题解和文章解析后做出来了 123.买卖股票的最佳时机III class Solution:def maxProfit(self, prices: List[int]) -> int:if len(prices) 0:return 0dp [[0] * 5 for _ in…...

11.20 知识总结(choices参数、MVC和MTV的模式、Django与Ajax技术)

一、 choices参数的使用 1.1 作用 针对某个可以列举完全的可能性字段&#xff0c;我们应该如何存储 .只要某个字段的可能性是可以列举完全的&#xff0c;那么一般情况下都会采用choices参数 1.2 应用场景 应用场景&#xff1a; 学历&#xff1a; 小学 初中 高中 本科 硕士…...

深度学习二维码识别 计算机竞赛

文章目录 0 前言2 二维码基础概念2.1 二维码介绍2.2 QRCode2.3 QRCode 特点 3 机器视觉二维码识别技术3.1 二维码的识别流程3.2 二维码定位3.3 常用的扫描方法 4 深度学习二维码识别4.1 部分关键代码 5 测试结果6 最后 0 前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天…...

C#关于TimeSpan结构的使用和获取两个时间差

C#中的TimeSpan结构可以获取两个时间的时间差。 它主要具有以下属性和方法&#xff1a; 属性&#xff1a; Days&#xff1a;获取时间间隔的天数部分。Hours&#xff1a;获取时间间隔的小时数部分&#xff08;不包括整天的小时数&#xff09;。Minutes&#xff1a;获取时间间…...

Xshell远程连接Kali(默认 | 私钥)Note版

前言:xshell远程连接&#xff0c;私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...

蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练

前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1)&#xff1a;从基础到实战的深度解析-CSDN博客&#xff0c;但实际面试中&#xff0c;企业更关注候选人对复杂场景的应对能力&#xff08;如多设备并发扫描、低功耗与高发现率的平衡&#xff09;和前沿技术的…...

(二)原型模式

原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...

跨链模式:多链互操作架构与性能扩展方案

跨链模式&#xff1a;多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈&#xff1a;模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展&#xff08;H2Cross架构&#xff09;&#xff1a; 适配层&#xf…...

HTML前端开发:JavaScript 常用事件详解

作为前端开发的核心&#xff0c;JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例&#xff1a; 1. onclick - 点击事件 当元素被单击时触发&#xff08;左键点击&#xff09; button.onclick function() {alert("按钮被点击了&#xff01;&…...

学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2

每日一言 今天的每一份坚持&#xff0c;都是在为未来积攒底气。 案例&#xff1a;OLED显示一个A 这边观察到一个点&#xff0c;怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 &#xff1a; 如果代码里信号切换太快&#xff08;比如 SDA 刚变&#xff0c;SCL 立刻变&#…...

AI,如何重构理解、匹配与决策?

AI 时代&#xff0c;我们如何理解消费&#xff1f; 作者&#xff5c;王彬 封面&#xff5c;Unplash 人们通过信息理解世界。 曾几何时&#xff0c;PC 与移动互联网重塑了人们的购物路径&#xff1a;信息变得唾手可得&#xff0c;商品决策变得高度依赖内容。 但 AI 时代的来…...

【Go语言基础【13】】函数、闭包、方法

文章目录 零、概述一、函数基础1、函数基础概念2、参数传递机制3、返回值特性3.1. 多返回值3.2. 命名返回值3.3. 错误处理 二、函数类型与高阶函数1. 函数类型定义2. 高阶函数&#xff08;函数作为参数、返回值&#xff09; 三、匿名函数与闭包1. 匿名函数&#xff08;Lambda函…...

Linux 中如何提取压缩文件 ?

Linux 是一种流行的开源操作系统&#xff0c;它提供了许多工具来管理、压缩和解压缩文件。压缩文件有助于节省存储空间&#xff0c;使数据传输更快。本指南将向您展示如何在 Linux 中提取不同类型的压缩文件。 1. Unpacking ZIP Files ZIP 文件是非常常见的&#xff0c;要在 …...

vulnyx Blogger writeup

信息收集 arp-scan nmap 获取userFlag 上web看看 一个默认的页面&#xff0c;gobuster扫一下目录 可以看到扫出的目录中得到了一个有价值的目录/wordpress&#xff0c;说明目标所使用的cms是wordpress&#xff0c;访问http://192.168.43.213/wordpress/然后查看源码能看到 这…...