企业官网建设流程全解析

LeetCode 111. 二叉树的最小深度

题目链接：111. 二叉树的最小深度

弄了个网站, 可以看代码是怎么操作达到最终要的结果: 过程可视化

如果还没有看过二叉树递归基础，可以先看：LeetCode 104. 二叉树的最大深度（递归解法）

这道题和 104 最大深度非常相似。

之前 104 要求找到根节点到最远叶子节点的距离。对于每个节点，我们只需要比较左右子树的最大深度，选择更深的一边，再加上当前节点本身的这一层。

因此，递归公式为：

当前节点的最大深度 = 1 + max(左子树最大深度, 右子树最大深度)

而 111 则要求找到最近的叶子节点。

表面上看，似乎只需要把max()换成min()？

但实际写起来就会发现，这里隐藏着一个容易忽略的问题 ~

一、先理解题目要求

二叉树的最小深度，指的是：

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

这里有两个需要注意的地方。

首先，深度计算的是节点数量，而不是经过的边数。例如1 -> 2 -> 3经过了两条边，但深度是 3。

其次，路径必须到达叶子节点才能结束。

所谓叶子节点，就是没有左孩子，也没有右孩子的节点。在 Python 中可以这样判断：

node.left is None and node.right is None

例如：

3 / \ 9 20 / \ 15 7

这棵树的叶子节点有9、15、7，其中距离根节点最近的是9。

对应路径为：

3 -> 9

这条路径包含 2 个节点，因此最小深度为2。

所以这道题是要找到根节点到某个真实叶子节点的最短路径。

二、第一反应：是不是直接使用 min？

看到这道题，我首先想到的是最大深度的递归写法。

如果还不熟悉递归求深度，可以先理解一个过程：

假设当前节点已经知道左子树和右子树各自的深度，那么它就可以在两个结果中选择一个，再加上当前节点本身的这一层。

例如最大深度的计算：

left_depth = find_depth(node.left) right_depth = find_depth(node.right) return max(left_depth, right_depth) + 1

其中，find_depth(node.left)会计算左子树的最大深度，右子树同理。

max()选择更深的一边，最后+1是把当前节点本身也算进去。

既然最大深度选择更长的一边，那么最小深度是不是只要选择更短的一边？

return min(left_depth, right_depth) + 1

乍一看，这个想法完全合理。

例如：

1 / \ 2 3

节点2和3都是叶子节点，因此它们各自返回的深度都是1。

到了根节点1，我们就能得到：

left_depth = 1 right_depth = 1 return min(1, 1) + 1 # 2

结果确实是 2，没有问题。

于是，我最开始写出了这样的递归：

class Solution: def minDepth(self, root: TreeNode | None) -> int: def find_depth(node): if node is None: return 0 left_depth = find_depth(node.left) right_depth = find_depth(node.right) return 1 + min(left_depth, right_depth) return find_depth(root)

这个写法和求最大深度几乎一样，只是把max()改成了min()。

但是它有一个很明显的漏洞：当一个节点只有左孩子或者只有右孩子时，计算结果就可能出错。

三、为什么不能直接 min(left_depth, right_depth)？

先来看一棵只有左子树的二叉树：

1 / 2 / 3

这棵树只有一个叶子节点3，所以最短路径只能是：

1 -> 2 -> 3

正确答案应该是3。

但是如果使用前面的代码，会发生什么？

我们从最底层开始分析。当递归计算到叶子节点3时，它的左右孩子都是None，因此：

left_depth = 0 right_depth = 0 return 1 + min(0, 0) # 1

这个结果没有问题，叶子节点本身的深度就是 1。

接下来递归返回到节点2。

节点2的左子树是节点3，所以left_depth = 1。

但是, 问题来了, 它没有右孩子，因此递归到右边时会返回0。

此时执行：

return 1 + min(1, 0)

得到的结果最终会是1！

可是节点2到最近叶子节点3的路径明明是：

2 -> 3

深度应该是 2。

所以, 问题出现了，min()把不存在的右子树当成了一条更短的路径。

这里的0原先只是用来表示子树不存在，到了叶子节点了, 在这里却被用于代表右边真的有一条长度为 0 的路径可以到达叶子节点。

因此，我们需要考虑到不存在的子树, 不能让它在直接返回 0 的时候 拿来比较。

所以, 在 104 最大深度中，空子树返回0没有问题，而到了 111 却会出错。

因为：

• 求最大深度时，max(1, 0)会选择真实存在的路径。
• 求最小深度时，min(1, 0)反而会选择不存在的路径。

所以这道题真正需要处理的，其实并不是如何求min()，而是如何判断哪条路径可以参与比较。

四、重新梳理递归思路

发现问题之后，我们需要重新确定递归函数的含义。

这里定义：

find_depth(node)

表示以当前节点为根的子树，到最近叶子节点的最小深度。

接下来就需要考虑几种情况。

情况 1：当前节点为空

当node is None时，说明当前子树不存在，因此返回0，作为递归的终止条件。

if node is None: return 0

不过要注意，这里的0不是有效的叶子路径深度。

如果后面需要使用min()，还得先确认左右子树是否真的存在。

情况 2：当前节点是叶子节点

例如：

1

因为节点1没有左右孩子，所以它本身就是叶子节点，最小深度为1。

我们可以直接判断：

if node.left is None and node.right is None: return 1

不过，这个条件并不是必须单独写出来的。

如果左右孩子都不存在，那么左右递归都会返回0。只要我们正确处理单侧为空的情况，最终同样可以得到0 + 1 = 1。

因此，后面的完整代码会直接使用单侧为空的判断，不再额外添加叶子节点的特殊判断。

情况 3：只有左子树

例如：

1 / 2

节点1只有左孩子，右边根本不存在能够到达叶子节点的路径。

既然只有左边可以走，我们就不应该再比较左右深度，而是直接使用左子树的结果：

if node.right is None: return left_depth + 1

这里的+1仍然表示把当前节点本身计算进去。

情况 4：只有右子树

同理，如果当前节点没有左孩子，那么只能沿着右子树寻找叶子节点。

if node.left is None: return right_depth + 1

情况 5：左右都有孩子

例如：

1 / \ 2 3

当左右子树都存在时，两边才都有可能找到叶子节点。

这时候我们就可以正常比较左右子树的最小深度，选择更短的一边：

return min(left_depth, right_depth) + 1

到这里，整个递归思路就清楚了。

递归求出左右子树深度 ↓ 左孩子为空？ / \ 是 否 ↓ ↓ 返回 right_depth+1 右孩子为空？ / \ 是 否 ↓ ↓ 返回 left_depth+1 返回 min(left_depth, right_depth)+1

五、完整代码

class Solution: def minDepth(self, root: TreeNode | None) -> int: def find_depth(node): if node is None: return 0 left_depth = find_depth(node.left) right_depth = find_depth(node.right) # 没有左孩子，只能走右边 if node.left is None: return right_depth + 1 # 没有右孩子，只能走左边 if node.right is None: return left_depth + 1 # 左右都有孩子，选择更短路径 return min(left_depth, right_depth) + 1 return find_depth(root)

六、代码关键点解释

1. 为什么这份代码没有单独判断叶子节点？

前面提到，叶子节点没有左右孩子，因此它的最小深度应该是1。

按照这个思路，我们似乎应该单独写一个判断：

if node.left is None and node.right is None: return 1

但在完整代码中，我们并没有这样写，为什么仍然能够正确处理叶子节点呢？

先看原来的代码：

left_depth = find_depth(node.left) right_depth = find_depth(node.right) if node.left is None: return right_depth + 1 if node.right is None: return left_depth + 1 return min(left_depth, right_depth) + 1

假设当前节点就是一个叶子节点：

3 / \ None None

由于左右孩子都是None，递归计算后，left_depth和right_depth都等于0。

接下来，程序遇到第一个判断：

if node.left is None: return right_depth + 1

这里需要注意，这个条件只要求左孩子为空，并没有规定右孩子必须存在。

所以无论是「只有右孩子」，还是「左右孩子都没有」，都会满足node.left is None。

当前节点恰好是叶子节点，左孩子当然也是None，因此条件成立，直接返回：

return 0 + 1 # 1

这样就得到了正确的叶子节点深度。

也就是说，虽然我们最初是为了处理单侧子树不存在的情况才写出这个判断，但它实际上也包含了左右子树都不存在的情况。

因此，叶子节点不是没有被处理，而是在第一个if判断中就已经返回了1，根本不会执行后面的判断。

📒 当然，如果觉得这种写法不够直观，也完全可以单独判断叶子节点。两种写法都正确，只是前者省略了一个可以被现有条件覆盖的判断。

2. 为什么空节点返回 0，却不会影响最后的 min()？

这也是前面一直在尝试解释、最容易产生疑惑的地方。

既然空节点返回0会导致min()计算错误，那为什么我们仍然保留：

if node is None: return 0

这里需要区分两个判断的作用。

• node is None负责结束空节点的递归，并将0传回上一层；
• 而下面的判断则负责检查当前节点是否缺少某一侧子树，避免将这个0当成有效路径参与比较。

if node.left is None: return right_depth + 1 if node.right is None: return left_depth + 1

例如：

1 / 2

当递归计算到节点1时，左子树中的节点2会返回深度1，而右子树不存在，因此返回0。

此时，节点1拿到的结果是：

left_depth = 1 right_depth = 0

注意，0确实已经传回来了，但程序还没有执行min()。

接下来，代码会先检查左右孩子是否存在：

if node.left is None: return right_depth + 1 if node.right is None: return left_depth + 1

由于节点1没有右孩子，第二个if条件成立，程序就会直接返回left_depth + 1，也就是2。

而一旦执行了return，当前这一层递归就结束了，后面的min()根本不会执行。

所以，问题不在于空节点能不能返回0，而在于父节点拿到这个0后，是否直接把它用于计算。

在我们的代码中，只有当左右孩子都存在时，程序才会执行：

return min(left_depth, right_depth) + 1

这样一来，空节点仍然可以返回0作为递归的终止结果，但它不会被错误地当成一条更短的路径。

换句话说，0可以传回父节点，只是父节点需要先判断它是否代表一条真实存在的路径，再决定如何使用这个返回值。

3. 空节点一定要返回 0 吗？能不能换一个值？

写到这里，我又想到一个问题：既然空节点返回0会被min()当成最短路径，那能不能换一个特殊值，让它不被选中呢？

例如，使用-1或者负无穷-inf？

但仔细想想就会发现，这样反而不行。因为我们使用的是min()，它会优先选择更小的数。如果空节点返回-1，那么min(2, -1)仍然会选择不存在的路径。

那反过来，如果使用正无穷inf呢？

min(2, float('inf')) # 2

这样一来，空节点虽然仍然参与了计算，但是由于它返回的是正无穷，min()就会自动选择另一条真实存在的路径，而不需要像之前那样分别判断只有左子树或只有右子树的情况。

不过，这里又出现了一个新的问题。如果当前节点本身就是叶子节点，它的左右孩子都会返回inf，于是：

1 + min(float('inf'), float('inf')) # inf

这显然不对。

叶子节点的最小深度应该是1，所以使用这种写法时，我们需要单独判断叶子节点。

另外，整棵树为空时，题目要求返回0，因此还需要在进入递归前处理空树。

这样就得到另一种写法：

class Solution: def minDepth(self, root: TreeNode | None) -> int: if root is None: return 0 def find_depth(node): if node is None: return float('inf') # 叶子节点的深度为 1 if node.left is None and node.right is None: return 1 left_depth = find_depth(node.left) right_depth = find_depth(node.right) return 1 + min(left_depth, right_depth) return find_depth(root)

例如，某个节点只有左子树，左子树返回深度2，而不存在的右子树返回inf，那么当前节点的结果就是：

1 + min(2, float('inf')) # 3

这样就能够正常得到最小深度。

所以，空节点并不是只能返回0，而是要看我们准备如何处理这个返回值。

• 返回0：需要提前判断左右子树是否存在，避免不存在的路径参与min()比较。
• 返回inf：可以让min()自动选择存在的路径，但需要单独处理叶子节点和整棵树为空的情况。

两种写法都正确，时间复杂度都是O(n)，递归栈空间复杂度都是O(h)。

这里最值得注意的是，不能只考虑递归终止时返回什么，还要考虑返回值传给父节点之后，会不会影响后面的计算。

这也是为什么有时候我们需要使用特殊值，有时候又需要额外添加判断。重点不在于选择哪个固定的返回值，而在于让返回值的含义和后续计算保持一致。

七、复杂度分析

• 时间复杂度：O(n)

  • 在最坏情况下，递归需要访问二叉树中的每一个节点。对于每个节点，我们只进行固定次数的判断和计算，因此整体时间复杂度为O(n)，其中n为二叉树的节点数量。

  • 虽然代码同时递归左右子树，但每个节点只会被访问一次，并不会因为有两个递归调用就变成O(n²)。

• 空间复杂度：O(h)

  • 递归需要使用调用栈保存当前执行路径，调用栈的最大深度取决于二叉树的高度h。

  • 如果二叉树比较平衡，空间复杂度为O(log n)；如果退化成一条链，最坏情况下则为O(n)。

八、最后复盘

回过头来看，这道题最初的想法并没有太大问题。

既然最大深度可以使用：

max(left_depth, right_depth) + 1

那么最小深度自然会想到：

min(left_depth, right_depth) + 1

真正的问题是，我们忽略了一条路径是否真实存在。

• 在求最大深度时，不存在的子树返回0，不会影响我们选择更长的路径；
• 但在求最小深度时，同样的0却可能被误认为是最短路径。

所以这道题并不是简单地把max()换成min()，而是需要在计算前判断左右子树是否存在。

这也是从 104 到 111 很值得注意的一点：虽然两道题都通过递归计算深度，但是我们不能只照搬递归公式，还需要思考返回值代表什么，以及这个返回值能否参与当前节点的计算。

以后遇到类似的递归题，可以尝试先去想三个问题：

1. 当前递归函数返回的结果代表什么？
2. 递归什么时候停止，终止时应该返回什么？
3. 父节点拿到子树的返回值之后，能不能直接使用？是否存在需要特殊处理的情况？