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

Create by jsliang on 2019-6-25 07:46:07
Recently revised in 2019-6-25 09:26:11

一 目录

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

目录
一 目录
二 前言
三 解题
3.1 解题 - 转数组

二 前言

返回目录

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

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

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

示例:

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

    3
   / \
  9  20
    /  \
   15   7
返回它的最小深度  2.

三 解题

返回目录

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

  • 解题代码
var minDepth = function(root) {
  if (!root) {
    return 0;
  }
  if (!root.left) {
    return minDepth(root.right) + 1;
  }
  if (!root.right) {
    return minDepth(root.left) + 1;
  }
  return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
};

四 执行测试

返回目录

  • root
const root = {
  val: 3,
  left: { val: 9, left: null, right: null },
  right: {
    val: 20,
    left: { val: 15, left: null, right: null },
    right: { val: 7, left: null, right: null },
  },
}
  • return
2
  • LeetCode Submit
√ Accepted
  √ 41/41 cases passed (80 ms)
  √ Your runtime beats 98.52 % of javascript submissions
  √ Your memory usage beats 8.64 % of javascript submissions (37.7 MB)

五 知识点

返回目录

  1. 六 解题思路

返回目录

说说 jsliang 的思路:

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

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

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

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

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


// root:
//   3
//  / \
// 9  20
//   /  \
//  15   7
const root = {
  val: 3,
  left: { val: 9, left: null, right: null },
  right: {
    val: 20,
    left: { val: 15, left: null, right: null },
    right: { val: 7, left: null, right: null },
  },
}
var minDepth = function(root) {
  if (!root) {
    return 0;
  }
  if (!root.left) {
    return minDepth(root.right) + 1;
  }
  if (!root.right) {
    return minDepth(root.left) + 1;
  }
  return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
};
minDepth(root);

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

图

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

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

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

Copyright © jsliang.top 2019 all right reserved,powered by Gitbook该文件修订时间: 2019-06-25 09:26:12

results matching ""

    No results matching ""