“二叉树的最大深度”，竟然有3家大厂在考这道算法题...
“二叉树的最大深度”，竟然有3家大厂在考这道算法题...
前言
最近至少有3个朋友在字节、小红书、蚂蚁的前端面试中遇到了同一道算法题，二叉树的最大深度...
作为leetcode大神的你想必早已露出了惊讶的眼神：“真的吗？这不过是一道简单题而已！！！”
“此事千真万确”胖头鱼敢打包票，简单题也有其面试的价值。让俺们一起瞅瞅这到底是啥题！
题目解析
查看原题
给定一个二叉树 root ，返回其最大深度。
二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：3
示例 2：
输入：root = [1,null,2]
输出：2
提示：
- 树中节点的数量在 [0, 104] 区间内。
- -100 <= Node.val <= 100
解析
根据题意我们不难看出二叉树的最大深度和二叉树的层数非常相似，一起来看看。
例子1
输入：root = [3,9,20,null,null,15,7]
输出：3
3 <-- 第 1 层
/ \
9 20 <-- 第 2 层
/ \
15 7 <-- 第 3 层
例子2
输入：root = [1,null,2]
输出：2
1 <-- 第 1 层
\
2 <-- 第 2 层
解法1：层序遍历
所以我们可以尝试从二叉树的层序遍历开始入手。
层序遍历： 是一种按层级顺序逐层遍历二叉树节点的方法。
从根节点开始，按层级顺序从上到下、从左到右依次访问每个节点。在遍历过程中，每一层的节点按照从左到右的顺序加入结果中。
对于示例 [3,9,20,null,null,15,7] 对应的二叉树如下所示：
3
/ \
9 20
/ \
15 7
层序遍历的结果为 [3, 9, 20, 15, 7]。
代码实现如下：
const levelOrder = (root) => {
if (!root) {
return []
}
const result = []
const queue = [ root ]
while (queue.length) {
// 取出队首节点
const top = queue.shift()
// 加入结果
result.push(top.val)
// 将左右节点加入队列
top.left && queue.push(top.left)
top.right && queue.push(top.right)
}
return result
}
利用队列的性质，我们可以拿到二叉树层序遍历的值，在此基础上只要我们稍微做一些改变就可以获得二叉树最大的深度。
求解二叉树最大的深度
const maxDepth = (root) => {
if (!root) {
return 0
}
// 层数
let depth = 0
const queue = [ root ]
while (queue.length) {
// 当前层的节点数，例如第一层是为1、第二层为2
let len = queue.length
depth++
while (len--) {
// 取出队首的元素
const top = queue.shift()
// 将左右节点加入队列
top.left && queue.push(top.left)
top.right && queue.push(top.right)
}
}
return depth
}
咱们以输入 root = [3,9,20,null,null,15,7] 为例，解析一下最终获取depth为3的过程。
首先是初始状态，根节点 3 被放入队列中：
queue：[3]
depth：0
首次进入外层while循环，depth增加1最终为1，并且进入内层while循环，内层while循环结束后
queue：[9, 20]
depth：1
再次进入外层while循环，depth增加1最终为2，并且进入内层while循环，内层while循环结束后
queue：[15, 7]
depth：2
最后一次进入外层while循环，depth增加1最终为3，并且进入内层while循环，内层while循环结束后。
queue：[]
depth：3
最后我们获得了最大层数3,也通过leetcode所有的用例测试。
解法二：递归
其中一个朋友看到这道题的时候，他内心大喜，但是又不能表现出来...
还得假装不会这个题，思考了10几秒，你说苦不苦😄，因为使用递归的话，几行代码就搞定了。
var maxDepth = function(root) {
if (!root) {
return 0
}
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1
}
我们可以这样理解这个解法：
一个树的最大深度 = 根节点的高度（即1）+ 左右子树的最大深度中的较大者。
拿输入为：[3,9,20,null,null,15,7] 为例
3
/ \
9 20
/ \
15 7
1. 根节点是 3，深度为1。
2. 左子树是 [9]，深度为1。
3. 右子树是 [20,null,null,15,7]，深度为2。
3.1 右子树的左子树是 15，深度为1。
3.2 右子树的右子树是 7，深度为1。
因此，整棵树的深度是左右子树深度的较大值加上1，即 max(1, 2) + 1 = 3，最大深度为3。最后
也许你我素未谋面，但很可能相见恨晚。希望这里能成为你的栖息之地，我愿和你一起收获喜悦，奔赴成长。