【递归】9. leetcode 104 二叉树的最大深度

devtools/2024/12/23 3:51:50/

1 题目描述

题目链接:二叉树的最大深度
在这里插入图片描述

2 解答思路

递归分为三步,接下来就按照这三步来思考问题

第一步:挖掘出相同的子问题  (关系到具体函数头的设计)
第二步:只关心具体子问题做了什么  (关系到具体函数体怎么写,是一个宏观的过程)
第三步:找到递归的出口,防止死递归  (关系到如何跳出递归)

2.1 相同的子问题(函数头设计)

相同的子问题:二叉树的最大深度:这棵树的左子树的深度和右子树的深度中的最大值 + 1

根据这句话,判断出函数头只需要传递一个参数,就是TreeNode* root

下面是leetcode的函数头:

    int maxDepth(TreeNode* root) {}

传入一个TreeNode* root的参数,返回二叉树的最大深度。

因此,我们可以直接使用leetcode给的函数头,不需要再自己创建。

2.2 具体的子问题做了什么(函数体的实现)

具体的子问题:找左子树的深度和右子树的深度的最大值 + 1

这里为什么要+1?

因为递归调用找到的子树的最大深度其实没有算上自己。因为只算上了子树的最大深度,所以要+1,算上自己的深度再返回。

递归的出口?

当节点为空的时候

代码实现:

    int maxDepth(TreeNode* root) {if (root == nullptr)return 0;//二叉树的最大深度:这棵树的左子树的深度和右子树的深度中的最大值 + 1return max(maxDepth(root->left), maxDepth(root->right)) + 1;}

在这里插入图片描述


http://www.ppmy.cn/devtools/120108.html

相关文章

实现微信小程序中点击单词显示在input的交互功能指南

✅作者简介:2022年博客新星 第八。热爱国学的Java后端开发者,修心和技术同步精进。 🍎个人主页:Java Fans的博客 🍊个人信条:不迁怒,不贰过。小知识,大智慧。 💞当前专栏…

JMeter压测HTTPS 在window 11处理SSL证书认证

在此位置,找到chrome 的证书 证书到出到指定的路径, 利用jdk中的keytool.exe工具,重新生成证书 crm 去到命令窗口,再去到JDK路径下,如下 输入 keytool -import -alias “zhengshu.store” -file “D:\Program F…

LeetCode[中等] 279.完全平方

给你一个整数 n ,返回 和为 n 的完全平方数的最少数量 。 完全平方数 是一个整数,其值等于另一个整数的平方;换句话说,其值等于一个整数自乘的积。例如,1、4、9 和 16 都是完全平方数,而 3 和 11 不是。 1…

某星球预约抢票脚本

Python脚本是一个自动化工具,用于监控即将开售的演出票务信息,并更新一个Markdown文件(`README.md`)来显示即将开售的演出列表。它利用了网络请求来获取信息,并对数据进行了处理和格式化,最后通过特定的API发送通知。让我们逐步分析这段代码的主要功能和组成部分。 类和函…

diffusion vs GAN

参考blog:深入浅出完整解析AIGC时代中GAN系列模型的前世今生与核心知识 diffusion vs GAN 对比 生成速度 GAN架构通常比Diffusion架构更快,因为GAN只需要一次前向传播即可生成样本,而Diffusion模型需要多次采样迭代来逐步生成最终图像。同时…

10款好用的开源 HarmonyOS 工具库

大家好,我是 V 哥,今天给大家分享10款好用的 HarmonyOS的工具库,在开发鸿蒙应用时可以用下,好用的工具可以简化代码,让你写出优雅的应用来。废话不多说,马上开整。 1. efTool efTool是一个功能丰富且易用…

前端BOM常用操作

BOM操作常用命令详解及代码案例 BOM(Browser Object Model)是浏览器对象模型,是浏览器提供的JavaScript操作浏览器的API。BOM提供了与网页无关的浏览器的功能对象,虽然没有正式的标准,但现代浏览器已经几乎实现了Java…

828华为云征文 | 利用FIO工具测试Flexus云服务器X实例存储性能

目录 一、Flexus云服务器X实例概要 1.1 Flexus云服务器X实例摘要 1.2 产品特点 1.3 存储方面性能 1.4 测评服务器规格 二、FIO工具 2.1 安装部署FIO 2.2 主要性能指标概要 三、进行压测 3.1 测试全盘随机读IO延迟 3.2 测试全盘随机写IO延迟 3.3 测试随机读IOPS 3.4…