LeetCode - 111 - 二叉树的最小深度(minimum-depth-of-binary-tree)

栏目: IT技术 · 发布时间: 5年前

内容简介:LeetCode - 111 - 二叉树的最小深度(minimum-depth-of-binary-tree)

Create by jsliang on 2019-6-25 07:46:07
Recently revised in 2019-6-25 09:31:27

一 目录

不折腾的前端,和咸鱼有什么区别

| 目录 | | --- | | 一 目录 | | 二 前言 | | 三 解题 | | 四 执行测试 | | 五 知识点 | | 六 解题思路 |

二 前言

  • 难度:简单

  • 涉及知识:树、深度优先搜索、广度优先搜索

  • 题目地址:https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/

  • 题目内容

  1. 给定一个二叉树,找出其最小深度。

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

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

  4. 示例:

  5. 给定二叉树 [3,9,20,null,null,15,7],

  6. 3

  7. / \

  8. 9 20

  9. / \

  10. 15 7

  11. 返回它的最小深度  2.

三 解题

小伙伴可以先自己在本地尝试解题,再回来看看 jsliang 的解题思路。

  • 解题代码

  1. var minDepth = function(root) {

  2. if (!root) {

  3. return 0;

  4. }

  5. if (!root.left) {

  6. return minDepth(root.right) + 1;

  7. }

  8. if (!root.right) {

  9. return minDepth(root.left) + 1;

  10. }

  11. return Math.min(minDepth(root.left), minDepth(root.right)) + 1;

  12. };

四 执行测试

  • root

  1. const root = {

  2. val: 3,

  3. left: { val: 9, left: null, right: null },

  4. right: {

  5. val: 20,

  6. left: { val: 15, left: null, right: null },

  7. right: { val: 7, left: null, right: null },

  8. },

  9. }

  • return

  1. 2

  • LeetCode Submit

  1. Accepted

  2. 41/41 cases passed (80 ms)

  3. Your runtime beats 98.52 % of javascript submissions

  4. Your memory usage beats 8.64 % of javascript submissions (37.7 MB)

五 知识点

Math:JS 中的内置对象,具有数学常数和函数的属性和方法。Math 详细介绍

六 解题思路

说说 jsliang 的思路:

假设我是一只蜘蛛,我在一颗大树最底下(根节点),开始往上爬。

每经过 1 米(1 个 val 节点),我就留下一个分身。

当我爬到最顶的时候,我就进行最后标记,并告诉分身,前面凉凉了,开始报数!

于是从我为 1 开始,一直到根节点的长度,就是这个分支的高度。

消掉这条分支后,继续其他分支……

  1. // root:

  2. // 3

  3. // / \

  4. // 9 20

  5. // / \

  6. // 15 7

  7. const root = {

  8. val: 3,

  9. left: { val: 9, left: null, right: null },

  10. right: {

  11. val: 20,

  12. left: { val: 15, left: null, right: null },

  13. right: { val: 7, left: null, right: null },

  14. },

  15. }

  16. var minDepth = function(root) {

  17. if (!root) {

  18. return 0;

  19. }

  20. if (!root.left) {

  21. return minDepth(root.right) + 1;

  22. }

  23. if (!root.right) {

  24. return minDepth(root.left) + 1;

  25. }

  26. return Math.min(minDepth(root.left), minDepth(root.right)) + 1;

  27. };

  28. minDepth(root);


不折腾的前端,和咸鱼有什么区别!

LeetCode - 111 - 二叉树的最小深度(minimum-depth-of-binary-tree)

jsliang 会每天更新一道 LeetCode 题解,从而帮助小伙伴们夯实原生 JS 基础,了解与学习算法与数据结构。

扫描上方二维码,关注 jsliang 的公众号,让我们一起折腾!

LeetCode - 111 - 二叉树的最小深度(minimum-depth-of-binary-tree)
jsliang 的文档库 由 梁峻荣 采用 知识共享 署名-非商业性使用-相同方式共享 4.0 国际 许可协议进行许可。
基于https://github.com/LiangJunrong/document-library上的作品创作。
本许可协议授权之外的使用权限可以从 https://creativecommons.org/licenses/by-nc-sa/2.5/cn/ 处获得。


以上所述就是小编给大家介绍的《LeetCode - 111 - 二叉树的最小深度(minimum-depth-of-binary-tree)》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

XForms Essentials

XForms Essentials

Micah Dubinko / O'Reilly Media, Inc. / 2003-08-27 / USD 29.95

The use of forms on the Web is so commonplace that most user interactions involve some type of form. XForms - a combination of XML and forms - offers a powerful alternative to HTML-based forms. By pro......一起来看看 《XForms Essentials》 这本书的介绍吧!

JSON 在线解析
JSON 在线解析

在线 JSON 格式化工具

SHA 加密
SHA 加密

SHA 加密工具

HEX HSV 转换工具
HEX HSV 转换工具

HEX HSV 互换工具