草庐IT

Leetcode.111 二叉树的最小深度

感觉画质不如…原神 2023-08-26 原文

题目链接

Leetcode.111 二叉树的最小深度 easy

题目描述

给定一个二叉树，找出其最小深度。

最小深度是从 根节点 到 最近叶子节点 的 最短路径上的节点数量。

说明: 叶子节点是指没有子节点的节点。

示例 1：

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

示例 2：

输入：root = [2,null,3,null,4,null,5,null,6]
输出：5

提示：

  • 树中节点数的范围在 [ 0 , 1 0 5 ] [0, 10^5] [0,105] 内
  • − 1000 < = N o d e . v a l < = 1000 -1000 <= Node.val <= 1000 −1000<=Node.val<=1000

解法：递归

我们要求的是 叶子结点 到 根结点 的最短路径。

我们设 l l l 和 r r r 分别是 当前结点 r o o t root root 的左子节点到根结点的最短路径长度 和 当前结点 r o o t root root 的右子节点到根结点的最短路径长度。

  • 如果 l = = 0 l ==0 l==0，返回 r + 1 r + 1 r+1
  • 如果 r = = 0 r == 0 r==0，返回 l + 1 l + 1 l+1
  • 否则返回 m i n { l , r } + 1 min\{l , r \} + 1 min{l,r}+1

时间复杂度： O ( n ) O(n) O(n)

C++代码：

class Solution {
public:
    int minDepth(TreeNode* root) {
        if(root == nullptr) return 0;
        int l = minDepth(root->left);
        int r = minDepth(root->right);

        if(l == 0) return r + 1;
        else if(r == 0) return l + 1;
        
        return min(l , r) + 1;
    }
};

Python代码：


class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        if root == None:
            return 0
        l = self.minDepth(root.left)
        r = self.minDepth(root.right)

        if l == 0:
            return r + 1
        elif r == 0:
            return l + 1
        else:
            return min(l , r) + 1
Leetcode111spanclasstoken算法递归

有关Leetcode.111 二叉树的最小深度的更多相关文章

  1. 深度学习部署：Windows安装pycocotools报错解决方法 - 2

    深度学习部署：Windows安装pycocotools报错解决方法1.pycocotools库的简介2.pycocotools安装的坑3.解决办法更多Ai资讯：公主号AiCharm本系列是作者在跑一些深度学习实例时，遇到的各种各样的问题及解决办法，希望能够帮助到大家。ERROR:Commanderroredoutwithexitstatus1:'D:\Anaconda3\python.exe'-u-c'importsys,setuptools,tokenize;sys.argv[0]='"'"'C:\\Users\\46653\\AppData\\Local\\Temp\\pip-instal

  2. Python 刷Leetcode题库，顺带学英语单词（31） - 2

    ValidPalindromeGivenastring,determineifitisapalindrome,consideringonlyalphanumericcharactersandignoringcases. [#125]Example:"Aman,aplan,acanal:Panama"isapalindrome."raceacar"isnotapalindrome.Haveyouconsiderthatthestringmightbeempty?Thisisagoodquestiontoaskduringaninterview.Forthepurposeofthisproblem

  3. ruby - 获取数组中的值并最小化某个类属性的最优雅的方法是什么？ - 2

    假设我有以下类(class):classPersondefinitialize(name,age)@name=name@age=ageenddefget_agereturn@ageendend我有一组Person对象。是否有一种简洁的、类似于Ruby的方法来获取最小(或最大)年龄的人？如何根据它对它们进行排序？ 最佳答案 这样做会:people_array.min_by(&:get_age)people_array.max_by(&:get_age)people_array.sort_by(&:get_age)

  4. ruby - 在 Ruby 中实现二叉树 - 2

    我一直在尝试在Ruby中实现BinaryTree类，但我得到了stackleveltoodeep错误，尽管我似乎没有在该特定代码段中使用任何递归:1.classBinaryTree2.includeEnumerable3.4.attr_accessor:value5.6.definitialize(value=nil)7.@value=value8.@left=BinaryTree.new#stackleveltoodeephere9.@right=BinaryTree.new#andhere10.end11.12.defempty?13.(self.value==nil)?true:

  5. 深度学习12. CNN经典网络 VGG16 - 2

    深度学习12.CNN经典网络VGG16一、简介1.VGG来源2.VGG分类3.不同模型的参数数量4.3x3卷积核的好处5.关于学习率调度6.批归一化二、VGG16层分析1.层划分2.参数展开过程图解3.参数传递示例4.VGG16各层参数数量三、代码分析1.VGG16模型定义2.训练3.测试一、简介1.VGG来源VGG（VisualGeometryGroup）是一个视觉几何组在2014年提出的深度卷积神经网络架构。VGG在2014年ImageNet图像分类竞赛亚军，定位竞赛冠军；VGG网络采用连续的小卷积核（3x3）和池化层构建深度神经网络，网络深度可以达到16层或19层，其中VGG16和VGG

  6. IDEA使用LeetCode插件 - 2

    前言我们习惯用idea编写、调试代码，在LeetCode上刷题时，如果能够在IDEA编写代码，并且做好代码管理，是一件事半功倍的事情。对于后续复习题目，做笔记也会非常便利。本文目的在于介绍LeetCodeEditor的使用，以及配置工具类，最终目录结构如下：note：放置笔记src：放置代码leetcode.editor.cn：插件LeetCodeEditor自动生成utils：自定义的工具包，可用于自动化输入测试用例，定义题目需要的类（结构体）out：运行测试时自动生成LeetCodeEditorGitHub：https://github.com/shuzijun/leetcode-edit

  7. ruby - 返回空白页的最小 Capybara/Poltergeist 测试 - 2

    看来我正在回顾SO帖子中采取的步骤:Capybara,PoltergeistandPhantomjsandgivinganemptyresponseinbody.(如果你愿意，可以将其标记为重复，但我包含了一个最小的独立测试用例和版本号。)问题我做错了什么吗？我可以运行另一个可能有助于隔离问题的最小测试吗？文件:pgtest.rbrequire'rubygems'require'capybara'require'capybara/dsl'require'capybara/poltergeist'modulePGTestincludeCapybara::DSLextendselfdeft

  8. ruby-on-rails - connect() 到 unix :/var/run/unicorn. 连接到上游时 sock 失败(111:连接被拒绝) - 2

    我遵循ruby​​onrails一个应用程序点击部署。数据库做得很好，即使我检查Rails控制台一切正常017/02/2615:34:17[error]18564#0:*31connect()tounix:/var/run/unicorn.sockfailed(111:Connectionrefused)whileconnectingtoupstream,client:121.52.156.57,server:_,request:"GET/HTTP/1.1",upstream:"http://unix:/var/run/unicorn.sock:/",host:"188.166.157

  9. ruby Hash 包括另一个哈希，深度检查 - 2

    进行这种深度检查的最佳方法是什么:{:a=>1,:b=>{:c=>2,:f=>3,:d=>4}}.include?({:b=>{:c=>2,:f=>3}})#=>true谢谢 最佳答案 我想我从那个例子中明白了你的意思(不知何故)。我们检查子哈希中的每个键是否在超哈希中，然后检查这些键的对应值是否以某种方式匹配:如果值是哈希，则执行另一次深度检查，否则，检查值是否相等:classHashdefdeep_include?(sub_hash)sub_hash.keys.all?do|key|self.has_key?(key)&&ifs

  10. ruby-on-rails - Ruby 获取深度嵌套的 JSON API 数据 - 2

    我有一个Rails应用程序，它从WorldWeatherOnlineAPI获取响应。我正在使用rest-clientgem，响应采用JSON格式。我使用以下方法解析响应:parsed_response=JSON.parse(response)parsed_response显然是一个散列。我需要的数据是哈希内的字符串，数组内的哈希，另一个数组内的哈希，另一个哈希内的另一个哈希内的字符串。最内层的嵌套散列在["hourly"]中，这是一个由8个散列组成的数组，每个散列有20个键，拥有各种天气参数的字符串值。数组中的每个哈希值都是一天中的不同时间(预测是每三小时一次，3*8=24小时)。因此

随机推荐