内容简介：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深度学习框架的对比
- 【深度好文】深度分析如何获取方法参数名
- 直观理解深度学习基本概念（小白入门深度学习）
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
