025 · Minimum Depth of Binary Tree

algorithm
Published

May 29, 2026

My First Thoughts

这道题和 019 · Maximum Depth of Binary Tree 很像。

019 问的是最大深度，这里问的是最小深度。第一反应会是：既然最大深度是左右两边取更大的那个，那最小深度是不是左右两边取更小的那个？

先看最基本的情况。

如果 root is None，说明这是一棵空树，没有任何节点，所以最小深度应该是 0：

if root is None:
    return 0

如果 root 不是空节点，就要看它的左右子树。

这里会自然想到：左子树有一个最小深度，右子树也有一个最小深度，那么当前树的最小深度应该就是：

1 + min(left_mindepth, right_mindepth)

这个想法在左右子树都存在的时候是对的。

例如：

      3
     / \
    9   20
       /  \
      15   7

左边到叶子节点 9 的深度是 1，右边到叶子节点的最小深度也是 2，当前根节点再加上自己，所以答案是：

1 + min(1, 2) = 2

但还要注意一种情况：如果其中一个子树是空的，不能直接把空子树的深度 0 当成一条已经到达叶子节点的路径。

比如：

    2
     \
      3
       \
        4

节点 2 的左子树是空的，但 2 不是叶子节点。最小深度不能从 2 往左走到空节点就结束，因为题目要求必须走到叶子节点。

所以如果左子树是空的，就只能继续走右子树：

if root.left is None:
    return 1 + MinDepth(root.right)

如果右子树是空的，就只能继续走左子树：

if root.right is None:
    return 1 + MinDepth(root.left)

这样就能写出一个完整版本：

def MinDepth(root):
    if root is None:
        return 0

    if root.left is None:
        return 1 + MinDepth(root.right)

    if root.right is None:
        return 1 + MinDepth(root.left)

    left_mindepth = MinDepth(root.left)
    right_mindepth = MinDepth(root.right)

    return 1 + min(left_mindepth, right_mindepth)

这个思路的核心判断是：只有当左右子树都存在时，才可以在左右最小深度里取 min。

Why That Is Not Enough

上面的思路是对的，已经覆盖了这道题最容易错的地方。

按这个逻辑写出来，就是这道题的正确解法。

特别是这两段判断：

if root.left is None:
    return 1 + MinDepth(root.right)

if root.right is None:
    return 1 + MinDepth(root.left)

已经避免了最常见的坑：当一边子树为空时，不会把空子树的深度 0 当成一条更短的路径。

接下来只是把最终答案整理得更明确：

  1. 函数名按 Python 习惯写成 minDepth
  2. 可以单独写出叶子节点的情况，让“到叶子节点才结束”更明显
  3. 把递归返回值的含义说清楚

minDepth(node) 返回的是：

从 node 出发，到最近叶子节点为止，路径上经过的节点数量。

所以空节点返回 0 只表示“这里没有树”。它不是一条有效的根到叶子节点路径。正因为这一点，你的代码才需要保留单子树分支：

if root.left is None:
    return 1 + minDepth(root.right)

if root.right is None:
    return 1 + minDepth(root.left)

整理之后，规则就是：

  • 空树返回 0
  • 叶子节点返回 1
  • 只有左子树时，只能走左子树
  • 只有右子树时，只能走右子树
  • 左右子树都存在时，才取更小的那边

Final Idea

最终解法可以直接沿着这个递归定义写。

先处理空树：

if root is None:
    return 0

然后处理叶子节点。叶子节点没有左孩子，也没有右孩子，所以从它自己到最近叶子节点，只经过它自己一个节点：

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

接下来处理只有一个孩子的情况。

如果左子树不存在，说明不能往左边选一条深度为 0 的路径。当前节点还没有到叶子节点，必须继续进入右子树：

if root.left is None:
    return 1 + minDepth(root.right)

右子树不存在时同理：

if root.right is None:
    return 1 + minDepth(root.left)

最后，只有当左右子树都存在时，才比较两边谁更浅：

return 1 + min(minDepth(root.left), minDepth(root.right))

这道题和最大深度最大的区别就在这里。

最大深度可以把空子树当作 0，然后直接取 max。因为 max(0, x) 会自然选择存在的那一边。

最小深度不能直接取 min，因为 min(0, x) 会错误地选择空子树。

Why It Works

递归函数 minDepth(root) 的含义是：返回从当前节点 root 到最近叶子节点的节点数量。

如果当前节点为空，返回 0，表示没有节点。

如果当前节点是叶子节点，最近的叶子节点就是它自己，所以返回 1。

如果当前节点只有一个孩子，那么最近叶子节点一定在这个存在的子树里面。空的那一边没有叶子节点，不能作为候选路径。

如果当前节点左右孩子都存在，那么最近叶子节点要么在左子树里，要么在右子树里。递归分别求出两边的最小深度，再取更小的那个，最后加上当前节点本身。

这几种情况覆盖了二叉树节点的所有形态，所以递归会得到整棵树的最小深度。

Code

def minDepth(root):
    if root is None:
        return 0

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

    if root.left is None:
        return 1 + minDepth(root.right)

    if root.right is None:
        return 1 + minDepth(root.left)

    return 1 + min(minDepth(root.left), minDepth(root.right))

Complexity

Time \(O(n)\) - 最坏情况下需要访问树中的每个节点一次
Space \(O(h)\) - 递归调用栈的深度等于树的高度 h，最坏情况下可以到 \(O(n)\)

Takeaway

最小深度题的关键不是简单地把最大深度里的 max 换成 min，而是先确认递归返回值代表的是“到叶子节点的有效路径”。空子树的深度 0 只表示没有节点，不表示已经找到一条更短的根到叶子路径。

← Quiz