二叉树的最小深度-LeetCode

二叉树的最小深度

🎯 问题描述（来源于LeetCode）

描述：
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。

• 示例：
  • 示例 1：

    输入：root = [3,9,20,null,null,15,7]
        3
       / \
      9  20
        /  \
       15   7
    输出：2
    解释：最短路径为 3 -> 9，共 2 个节点。

  • 示例 2：

    输入：root = [2,null,3,null,4,null,5,null,6]
        2
         \
          3
           \
            4
             \
              5
               \
                6
    输出：5
    解释：这是一棵单边树（类似链表），最短路径就是整条链，共 5 个节点。

💻 解题思路

思路1：递归（DFS 自底向上）

代码实现

from typing import Optional

class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        
        # 提前计算深度，避免最后一行重复递归调用
        left_depth = self.minDepth(root.left)
        right_depth = self.minDepth(root.right)
        
        # 核心逻辑：处理单边树的情况
        if not root.left:
            return right_depth + 1
        if not root.right:
            return left_depth + 1
            
        # 左右子树都有，取较小值
        return min(left_depth, right_depth) + 1

📊 性能分析

• 时间复杂度：$O(n)$。每个节点只会被访问一次。
• 空间复杂度：$O(h)$。取决于树的高度（递归栈深度）。

💡 思考

这道题和“最大深度”最大的区别在于对空子树的处理：

• 最大深度：可以直接取 max(左, 右) + 1，因为空的那边是 0，不影响取最大值。
• 最小深度：不能直接取 min(左, 右) + 1。如果直接取最小值，当某一边为空（深度为 0）时，会错误地返回 1（把非叶子节点当成了叶子节点）。因此，必须先判断左右子树是否为空，如果是单边树，必须走有子树的那一边。