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

力扣日记11.27-【二叉树篇】二叉树的最大深度

力扣日记:【二叉树篇】二叉树的最大深度

日期:2023.11.27
参考:代码随想录、力扣

104. 二叉树的最大深度

题目描述

难度:

给定一个二叉树 root ,返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

示例 1:

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

示例 2:

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

提示:

  • 树中节点的数量在 [0, 10^4] 区间内。
  • -100 <= Node.val <= 100

题解

递归法(cpp ver)
/*** 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:// 递归法:后序遍历 (实际上是求高度)// 1. 确定递归函数的参数和返回值:参数就是传入树的根节点,返回就返回以该节点为根的树的深度int getdepth(TreeNode* node) {  // 2. 确定终止条件:如果为空节点的话,就返回0,表示高度为0。if (node == NULL) return 0;// 3. 确定单层递归的逻辑:先求它的左子树的深度,再求右子树的深度,最后取左右深度最大的数值 再+1 (加1是因为算上当前中间节点)就是目前节点为根节点的树的深度。int leftdepth = getdepth(node->left);       // 左(左子树的高度)int rightdepth = getdepth(node->right);     // 右(右子树的高度)int depth = 1 + max(leftdepth, rightdepth); // 中(左子树和右子树的根节点的高度, 包括根节点, 故+1)return depth;}int maxDepth(TreeNode* root) {return getdepth(root);}
};
迭代法(go ver)
/*** Definition for a binary tree node.* type TreeNode struct {*     Val int*     Left *TreeNode*     Right *TreeNode* }*/
func maxDepth(root *TreeNode) int {// 使用迭代法的话,使用层序遍历是最为合适的,因为最大的深度就是二叉树的层数,和层序遍历的方式极其吻合queue := list.New()maxDepth := 0if root != nil {queue.PushBack(root)}for queue.Len() > 0 {// 记录当前队列长度size := queue.Len()for size > 0 {// 弹出并写入结果front := queue.Front()node := queue.Remove(front).(*TreeNode) // 存进list之后类型会变为*list.Element,要转换为*TreeNode// 左右节点入队列if node.Left != nil {queue.PushBack(node.Left)}if node.Right != nil {queue.PushBack(node.Right)}size -= 1}maxDepth += 1}return maxDepth
}

复杂度

时间复杂度:
空间复杂度:

思路总结

  • 本题如果用迭代法,则直接使用层序遍历的模板解题即可
  • 如果用递归法,则相对难一些:
    • 首先要理解二叉树的深度高度区别:
      • 二叉树节点的深度:指从根节点该节点的最长简单路径边的条数或者节点数(取决于深度从0开始还是从1开始)—— 即深度是从某节点角度往上(根节点)看的
      • 二叉树节点的高度:指从该节点叶子节点的最长简单路径边的条数或者节点数(取决于高度从0开始还是从1开始)—— 即高度是从某节点角度往下(叶子节点)看的
      • 因此,根节点的高度就是二叉树的最大深度
    • 本题可以使用前序(中左右),也可以使用后序遍历(左右中),使用前序求的就是深度,即最大的叶子节点深度,使用后序求的是高度,即根节点的高度。(后序遍历相对容易理解一些,见代码)

相关文章:

力扣日记11.27-【二叉树篇】二叉树的最大深度

力扣日记&#xff1a;【二叉树篇】二叉树的最大深度 日期&#xff1a;2023.11.27 参考&#xff1a;代码随想录、力扣 104. 二叉树的最大深度 题目描述 难度&#xff1a; 给定一个二叉树 root &#xff0c;返回其最大深度。 二叉树的 最大深度 是指从根节点到最远叶子节点的最…...

【数据结构】树的概念以及二叉树

目录 1 树概念及结构 1.1 树的概念 1.3 树的存储 2 二叉树的概念及结构 2.1 概念 2.2 特殊的二叉树 2.3 二叉树的性质 2.4 二叉树的存储结构 1 树概念及结构 1.1 树的概念 树是一种非线性的数据结构&#xff0c;它是由n&#xff08;n>0&#xff09;个有限结点组…...

软件测试职业规划导图

公司开发的产品专业性较强&#xff0c;软件测试人员需要有很强的专业知识&#xff0c;现在软件测试人员发展出现了一种测试管理者不愿意看到的景象&#xff1a; 1、开发技术较强的软件测试人员转向了软件开发(非测试工具开发)&#xff1b; 2、业务能力较强的测试人员转向了软件…...

360压缩安装一半不动了?一分钟解决!

360压缩软件是我们常用的压缩软件&#xff0c;但是常常会遇到压缩安装到一半停止的情况&#xff0c;下面提供了一些可能的原因和解决办法&#xff0c;大家可以进行尝试~ 方法一&#xff1a;关闭防火墙和杀毒软件 有时候&#xff0c;防火墙和杀毒软件可能会阻止360压缩的安装过…...

堆和栈的区别 重点来说一下堆和栈;堆与栈之间的联系

文章目录 堆和栈的区别重点来说一下堆和栈&#xff1a;那么堆和栈是怎么联系起来的呢? 堆与栈的区别 很明显&#xff1a; 今天来聊一聊java中的堆和栈&#xff0c;工作当中这两个也是经常遇到的&#xff0c;知识我们没有去注意理论上的这些内容&#xff0c;今天就来分享一下。…...

python 批量将图片存入excel单元格内

python 批量将图片存入excel单元格 示例代码1示例代码2 示例代码1 https://blog.csdn.net/wuyoudeyuer/article/details/128185284 # -*- coding: utf-8 -*- # Time : 2022-12-05 # Author : Carl_DJ 实现功能&#xff1a;在excel中&#xff0c;对应的名称后面&#xff0c;…...

Nginx常见的中间件漏洞

目录 1、Nginx文件名逻辑漏洞 2、Nginx解析漏洞 3、Nginx越权读取缓存漏洞 这里需要的漏洞环境可以看&#xff1a;Nginx 配置错误导致的漏洞-CSDN博客 1、Nginx文件名逻辑漏洞 该漏洞利用条件有两个&#xff1a; Nginx 0.8.41 ~ 1.4.3 / 1.5.0 ~ 1.5.7 php-fpm.conf中的s…...

Linux C语言 27-递归

Linux C语言 27-递归 本节关键字&#xff1a;C语言 递归 相关C库函数&#xff1a;main、printf 什么是递归&#xff1f; 在C语言中&#xff0c;程序调用自身的编程技巧称为递归&#xff08;recursion&#xff09;。递归从字面上可以理解为“递去归来”。 使用递归的优缺点 …...

redis运维(二十一)redis 的扩展应用 lua(三)

一 redis 的扩展应用 lua redis加载lua脚本文件 ① 调试lua脚本 redis-cli 通过管道 --pipe 快速导入数据到redis中 ② 预加载方式 1、错误方式 2、正确方式 "案例讲解" ③ 一次性加载 执行命令&#xff1a; redis-cli -a 密码 --eval Lua脚本路径 key …...

如何科学地划分医学图像数据集

在进行医学图像分类任务时&#xff0c;如何科学地划分数据集是一个重要的问题。这个问题的答案取决于你的数据特性和实验目标。一般来说&#xff0c;有两种常见的数据划分方法&#xff1a;按照比例划分和按照病例划分。 按照比例划分 按照比例划分是一种常见的方法&#xff0c…...

【开源】基于Vue+SpringBoot的食品生产管理系统

项目编号&#xff1a; S 044 &#xff0c;文末获取源码。 \color{red}{项目编号&#xff1a;S044&#xff0c;文末获取源码。} 项目编号&#xff1a;S044&#xff0c;文末获取源码。 目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 加工厂管理模块2.2 客户管理模块2.3…...

如何减少40%的Docker构建时间

随着Docker的普及&#xff0c;许多公司的产品会将组件构建为Docker镜像。但随着时间的推移&#xff0c;一些镜像变得越来越大&#xff0c;对应的CI构建也变得越来越慢。 如果能在喝完一杯咖啡的时间&#xff08;不超过5分钟&#xff09;内完成构建&#xff0c;将是一个理想状态…...

Scrapy爬虫异步框架之持久化存储(一篇文章齐全)

1、Scrapy框架初识&#xff08;点击前往查阅&#xff09; 2、Scrapy框架持久化存储 3、Scrapy框架内置管道&#xff08;点击前往查阅&#xff09; 4、Scrapy框架中间件&#xff08;点击前往查阅&#xff09; Scrapy 是一个开源的、基于Python的爬虫框架&#xff0c;它提供了…...

JVM——几种常见的对象引用

目录 1. 软引用软引用的使用场景-缓存 2.弱引用3.虚引用和终结器引用 可达性算法中描述的对象引用&#xff0c;一般指的是强引用&#xff0c;即是GCRoot对象对普通对象有引用关系&#xff0c;只要这层关系存在&#xff0c; 普通对象就不会被回收。除了强引用之外&#xff0c;Ja…...

C++期末考试选择题题库100道C++期末判断题的易错知识点复习

今天备考C&#xff0c;看到了一些好的复习资料&#xff0c;整合一起给大家分享一下 选择题 对于常数据成员&#xff0c;下面描述正确的是 【 B 】 A. 常数据成员必须被初始化&#xff0c;并且不能被修改 B. 常数据成员可以不初始化&#xff0c;并且不能被修改 C. 常数据成…...

使用qemu调试arm内核

参考书籍《奔跑吧Linux内核》–笨叔 下载Linux-5.0源码 https://benshushu.coding.net/public/runninglinuxkernel_5.0/runninglinuxkernel_5.0/git/files或者直接git源码 git clone https://e.coding.net/benshushu/runninglinuxkernel_5.0/runninglinuxkernel_5.0.git安装必…...

Pytorch深度学习实战2-1:详细推导Xavier参数初始化(附Python实现)

目录 1 参数初始化2 Xavier参数初始化原理2.1 前向传播阶段2.2 反向传播阶段2.3 可视化思考 3 Python实现 1 参数初始化 参数初始化在深度学习中起着重要的作用。在神经网络中&#xff0c;参数初始化是指为模型中的权重和偏置项设置初始值的过程。合适的参数初始化可以帮助模型…...

Java的threadd常用方法

常用API 给当前线程命名 主线程 package com.itheima.d2;public class ThreadTest1 {public static void main(String[] args) {Thread t1 new MyThread("子线程1");//t1.setName("子线程1");t1.start();System.out.println(t1.getName());//获得子线程…...

一键修复0xc000007b错误代码,科普关于0xc000007b错误的原因

最近很多用户都有遇到过0xc000007b错误的问题&#xff0c;出现这样的问题想必大家都会手足无措吧&#xff0c;其实解决这样的问题也有很简单的解决方法&#xff0c;这篇文章就来教大家如何一键修复0xc000007b&#xff0c;同时给大家科普一下关于0xc000007b错误的原因&#xff0…...

使用Selenium、Python和图鉴打码平台实现B站登录

selenium实战之模拟登录b站 基础知识铺垫&#xff1a; 利用selenium进行截图&#xff1a; driver.save_screenshot() 注意图片文件名要用png结尾. 关于移动&#xff1a; ActionChains(bro).move_to_element_with_offset()# 对于某个图像ActionChains(bro).move_by_offset(…...

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 //第一…...

在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能

下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能&#xff0c;包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...

三维GIS开发cesium智慧地铁教程(5)Cesium相机控制

一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点&#xff1a; 路径验证&#xff1a;确保相对路径.…...

大语言模型如何处理长文本?常用文本分割技术详解

为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...

postgresql|数据库|只读用户的创建和删除(备忘)

CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...

【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)

升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点&#xff0c;但无自动故障转移能力&#xff0c;Master宕机后需人工切换&#xff0c;期间消息可能无法读取。Slave仅存储数据&#xff0c;无法主动升级为Master响应请求&#xff…...

Android Bitmap治理全解析:从加载优化到泄漏防控的全生命周期管理

引言 Bitmap&#xff08;位图&#xff09;是Android应用内存占用的“头号杀手”。一张1080P&#xff08;1920x1080&#xff09;的图片以ARGB_8888格式加载时&#xff0c;内存占用高达8MB&#xff08;192010804字节&#xff09;。据统计&#xff0c;超过60%的应用OOM崩溃与Bitm…...

DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”

目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...

CVE-2020-17519源码分析与漏洞复现(Flink 任意文件读取)

漏洞概览 漏洞名称&#xff1a;Apache Flink REST API 任意文件读取漏洞CVE编号&#xff1a;CVE-2020-17519CVSS评分&#xff1a;7.5影响版本&#xff1a;Apache Flink 1.11.0、1.11.1、1.11.2修复版本&#xff1a;≥ 1.11.3 或 ≥ 1.12.0漏洞类型&#xff1a;路径遍历&#x…...

【从零学习JVM|第三篇】类的生命周期(高频面试题)

前言&#xff1a; 在Java编程中&#xff0c;类的生命周期是指类从被加载到内存中开始&#xff0c;到被卸载出内存为止的整个过程。了解类的生命周期对于理解Java程序的运行机制以及性能优化非常重要。本文会深入探寻类的生命周期&#xff0c;让读者对此有深刻印象。 目录 ​…...