Leetcode 104. 二叉树的最大深度 C++实现

Leetcode 104. 二叉树的最大深度

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

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

25f68f8bc0f64a6b951ebaf471cc795f.png

/*** 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) {}* };*/

方法1:递归法 。自底向上

6ec1197bef7543cdabf683aa2bbd0088.png

434eb91071f7483982e2c0dd563e433a.png

55fbe3b66f9f479293f2e6856bef2ab5.png

时间复杂度:O(n),其中 n 为二叉树的节点个数。

空间复杂度:O(n),最坏情况下,二叉树退化成一条链,递归需要 O(n) 的栈空间。

代码:

class Solution {
public:int maxDepth(TreeNode* root) {if(root == nullptr) return 0;int leftdepth = maxDepth(root->left);int rightdepth = maxDepth(root->right);return max(leftdepth,rightdepth) + 1;}
};

方法2:自顶向下

定义一个全局变量 ans ,每向下递归一次就更新一次 ans 的值,遍历完成后 ans 的值就是答案。

代码:

class Solution {int ans = 0;// 初始化全局变量ansvoid dfs(TreeNode* node,int depth){if(node == nullptr) return;depth++;ans = max(ans,depth);dfs(node->left,depth);dfs(node->right,depth);}
public:int maxDepth(TreeNode* root) {dfs(root,0);return ans;}
};

时间复杂度:O(n),其中 n 为二叉树的节点个数。

空间复杂度:O(n),最坏情况下,二叉树退化成一条链,递归需要 O(n) 的栈空间。

 

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

培训第三十五天(容器的基础命令使用)

1、创建一个容器并同时执行echo命令 # 快速启动一个容器执行特定的一次性命令并查看输出结果,输出结果后容器直接退出[rootdocker ~]# docker run -it --namea0 centos:latest echo "abc"abc[rootdocker ~]# docker psCONTAINER ID IMAGE COMMAND …

游戏app激励视频广告预加载位置,最大化广告收益

最近收到很多游戏类App开发者咨询激励视频广告,在帮助开发者分析产品的时候,特别是一些初级开发者的App产品,发现用户进入这些App,或者打开某个功能时就弹出激励视频广告,这样是违规的,并且用户看完广告也是…

使用gitee存储项目

gitee地址:Gitee - 基于 Git 的代码托管和研发协作平台 创建gitee远程仓库 将远程仓库内容拉取到本地仓库 复制下面这个地址 通过小乌龟便捷推送拉取代码:https://blog.csdn.net/m0_65520060/article/details/140091437

数字图像处理【15】特征检测——SIFT特征检测

一、引入SIFT算法 上一篇文章我们重温学习了Harris角点检测算法的基本原理,但在实际生产使用Harris检测角点的时候,会发现一个问题,就是用于检测的输入图像的尺寸大小会直接影响到Harris的检测结果。这是为什么呢?主要是Harris角…

2024最新50道NLP和人工智能领域面试题+答案(中文+英文双版本)

编者按:分享一个很硬核的免费人工智能学习网站,通俗易懂,风趣幽默, 可以当故事来看,轻松学习。 中文版本 自然语言处理 (NLP)已成为语言学、人工智能和计算机科学交叉领域的变革性领域。随着文本数据量的不断增加&…

内网横向移动常用方法

横向移动 #横向移动含义 横向移动是以已经被攻陷的系统为跳板,通过收集跳板机的信息(文档,存储的凭证,ipc连接记录等等信息)来访问其他域内主机。#常见横向手段 1,通过相同的用户名密码批量ipc连接其他域内…

【学习笔记】Day 22

一、进度概述 1、机器学习常识23-24,以及相关代码复现 2、python 补完计划(详见 python 专题) 二、详情 23、U-Net 从宏观结构上来讲(以下摘自常识23): U-Net 就是 U 形状的网络, 前半部分 (左边…

三星计划今年HBM4设计,2025年初开始样品测试

三星计划今年晚些时候完成首款HBM4内存设备的设计定稿,2025年初开始样品测试 根据nN Elec援引行业消息人士的报道,三星计划在今年晚些时候完成首款HBM4内存设备的设计定稿,并预计将于2025年初开始样品测试。该公司预计将采用其最新一代10纳米…

详细分析 el-progress的基本知识以及用法(附Demo)

目录 前言1. 基本知识2. Demo3. 实战 前言 由于实战项目中有所引用,对此记录基本的知识点,并且以Demo的形式呈现 1. 基本知识 el-progress 是 Element Plus UI 库中的一个进度条组件,用于显示任务的完成情况 可以帮助用户了解某个操作或任…

[数据集][目标检测]工程机械车辆检测数据集VOC+YOLO格式3189张10类别

数据集格式:Pascal VOC格式YOLO格式(不包含分割路径的txt文件,仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数):3189 标注数量(xml文件个数):3189 标注数量(txt文件个数):3189 标注…

密码生成器(HTML+CSS+JavaScript)

🌏个人博客主页:心.c ​ 前言:前两天写了密码生成器,现在跟大家分享一下,大家如果想使用随便拿,如果哪里有问题还请大佬们给我指出,感谢支持 🔥🔥🔥专题文章&…

Vue3集成高德离线地图实践

1. 离线地图效果预览 2. 地图下载器下载离线地图 根据需要选择地图,我这边选择高德地图,层级选择0-15级别即可,进行下载 3. 放到nginx内网服务器 注意配置允许跨域 4. Vue3核心代码 // main.js // 初始化vue-amap initAMapApiLoader({o…

Android自定义简单TextView

自定义属性 <declare-styleable name"TextView"><!--name 属性名称format 格式&#xff1a;string 文字 color颜色dimension 宽高 字体大小 integer数字reference 资源引用(drawable)--><attr name"YiRanText" format"string"/&…

torchvision中的数据集使用

1.数据集&#xff1a; 自定义数据集transforms中的类 如何将数据集和transforms结合在一起&#xff1f; 以CIFAR10为列 2.CIFAR10数据集的下载与导入 import torchvisiontrain_settorchvision.datasets.CIFAR10(root"./dataset",trainTrue,downloadTrue) test_set…

判别分析2|Bayes判别分析|Fisher判别分析|软件求解

Bayes判别分析 引入先验信息 距离判别只要求知道总体的数字特征&#xff0c;不涉及总体的分布函数 当均值和协方差未知时&#xff0c;就用样本的均值和协方差矩阵做估计值。距离判别方法简单实用&#xff0c;但没有考虑到每个总体出现的机会大小&#xff0c;即先验概率&#…

Git的使用教程及常用语法03

七.如何从版本库中删除文件 第一种方式&#xff1a;直接在工作区删除文件&#xff0c;然后提交 rm ffile1.txt (注意&#xff1a;这个不是git命令&#xff0c;而是linux命令) 看到状态发现&#xff0c;文件file1.txt已经被删除&#xff0c;提示需要提交到暂存区。 因为我们只…

从开发到集成:视频美颜SDK与直播美颜API详解

在本文中&#xff0c;我们将详细探讨视频美颜SDK的开发过程及其与直播美颜API的集成方案&#xff0c;帮助开发者更好地理解和应用这些技术。 一、视频美颜SDK的开发概述 视频美颜SDK是一个用于实时视频处理的开发工具包&#xff0c;提供了包括磨皮、美白、瘦脸、眼睛放大等多…

盘古信息IMS MCM制造协同管理系统:为中小企业数字化转型量身打造的数字化方案

近年来&#xff0c;全球经济的不稳定性&#xff0c;给中小企业的经营和发展带来了巨大的挑战。为提升企业竞争力&#xff0c;中小企业纷纷谋求数字化转型路径&#xff0c;优化生产流程、提高运营效率、降低生产成本&#xff0c;以应对变幻莫测的市场环境。IMS MCM是盘古信息为广…

python爬虫521

爬虫521 记录 记录 最近想学爬虫&#xff0c;尝试爬取自己账号下的文章标题做个词云 csdn有反爬机制 原理我就不说啦 大家都写了 看到大家结果是加cookie 但是我加了还是521报错 尝试再加了referer 就成功了(╹▽╹) import matplotlib import requests from wordcloud impor…

TinaSDKV2.0 自定义系统开发

TinaSDKV2.0 自定义系统开发 什么是自定义系统&#xff1f; TinaSDK Kconfig界面配置 Tina Linux采用 Kconfig 机制对 SDK 和内核进行配置。 Kconfig 是一种固定格式的配置文件。Linux 编译环境中的 menuconfig 程序可以识别这种格式的配置文件&#xff0c;并提取出有效信息…