LeetCode - 104 - 二叉树的最大深度（maximum-depth-of-binary-tree）

内容简介：LeetCode - 104 - 二叉树的最大深度（maximum-depth-of-binary-tree）

Create by jsliang on 2019-06-14 16:18:02
Recently revised in 2019-06-14 17:15:44

一 目录

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

| 目录 | | --- | | 一 目录 | | 二 前言 | | 三 解题 | | 四 执行测试 | | 五 LeetCode Submit | | 六 解题思路 | | 七 进一步思考 |

二 前言

• 难度：简单

• 涉及知识：树

• 题目地址：深度优先搜索

• 题目内容：

给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7]，
    3
   / \
  9  20
    /  \
   15   7
返回它的最大深度 3 。

三 解题

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

• 解题代码：

var maxDepth = function(root) {
  if (!root) {
    return 0;
  }
  let longest = 1;
  let ergodic = function(root, depth) {
    if (!root) {
      return;
    }
    if (root.left || root.right) {
      depth += 1;
      if (depth > longest) {
        longest = depth;
      }
      ergodic(root.left, depth);
      ergodic(root.right, depth);
    }
  }
  ergodic(root, 1);
  return longest;
};

四 执行测试

• 参数 root：

let 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：

3

五 LeetCode Submit

✔ Accepted
  ✔ 39/39 cases passed (92 ms)
  ✔ Your runtime beats 91.94 % of javascript submissions
  ✔ Your memory usage beats 12.78 % of javascript submissions (37.4 MB)

六 解题思路

首先，如果小伙伴们还记得我们的万能公式：

let traverse = function(root) {
  // root 需要做什么？在这做。
  // 其他的不用 root 操心，抛给框架
  traverse(root.left);
  traverse(root.right);
}

那么你或许已经有思路了。

然后，为了方便从没接触过树解法的小伙伴们，jsliang 将这道题解题思路从头讲讲：

• 步骤 1：判断非空。如果是空的直接返回 0。

if (!root) {
  return 0;
}

• 步骤 2：由于前面判断非空了，所以现在最长的深度是 1，我们从 1 继续。

let longest = 1;

• 步骤 3：基于破解二叉树套路，开始解题。

let ergodic = function(root, depth) {
  if (!root) {
    return;
  }
  if (root.left || root.right) {
    depth += 1;
    if (depth > longest) {
      longest = depth;
    }
    ergodic(root.left, depth);
    ergodic(root.right, depth);
  }
}
ergodic(root, 1);

在这里，我们判断 root 是否还存在 left 和 right：如果不存在，那么树到了最底层，终止递归；如果存在，那么 depth 深度 +1，并且遍历它的左树和右树。

同时，我们在树存在 left 和 right 的时候，将 depth 和 longest 比较，把最深的树给记录下来。

• 步骤 4：返回最长深度 longest。

最后，我们就完成了这道求树最大深度的破解，小伙伴们是不是感觉思路一下子打开了？

那么，我们继续看下去。

七 进一步思考

jsiang 破解完这道题后，逛了下这道题的【题解】和【评论】，看到了一个优秀的代码，深感惭愧：

var maxDepth = function(root) {
  if(!root) return 0;
  return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
};

震惊有木有，哈哈，直接两行代码搞定！

但是，这还不是最佳的：

var maxDepth = function(root) {
  return root === null ? 0 : Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
};

好的吧，一行代码搞定了……面壁去！哈哈

---

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

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

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

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

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

查看所有标签

猜你喜欢:

• 沈向洋：从深度学习到深度理解
• 深度重建：基于深度学习的图像重建
• 深度网络揭秘之深度网络背后的数学
• 深度解析Python深度学习框架的对比
• 【深度好文】深度分析如何获取方法参数名
• 直观理解深度学习基本概念（小白入门深度学习）

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