111、二叉树的最小深度

class Solution:def getDepth(self, node):if node is None:  # 基本情况：空节点的深度为0return 0# 递归计算左右子树的深度leftDepth = self.getDepth(node.left)  # 左子树深度rightDepth = self.getDepth(node.right)  # 右子树深度# 处理只有单边子树的情况if node.left is None and node.right is not None:return 1 + rightDepth  # 只有右子树，深度取决于右子树if node.left is not None and node.right is None:return 1 + leftDepth  # 只有左子树，深度取决于左子树# 正常情况：取左右子树深度的较小值加1result = 1 + min(leftDepth, rightDepth)return resultdef minDepth(self, root):return self.getDepth(root)  # 调用getDepth计算最小深度

让我们用以下二叉树作为例子：

        1/ \2   3/ \4   5/6

计算过程详解

1. 初始调用 minDepth(1) → 调用 getDepth(1)

   • 节点1不为空
   • 计算左子树深度：getDepth(2)
   • 计算右子树深度：getDepth(3)

2. 计算 getDepth(2)

   • 节点2不为空
   • 左子树深度：getDepth(4) → 返回1（4是叶子节点）
   • 右子树深度：getDepth(5)
     • getDepth(5):
       • 左子树深度：getDepth(6) → 返回1（6是叶子节点）
       • 右子树深度：getDepth(None) → 返回0
       • 5有左子树无右子树 → 返回1 + leftDepth = 2
   • 2有左右子树 → 返回1 + min(1, 2) = 2

3. 计算 getDepth(3)

   • 节点3是叶子节点 → 返回1

4. 回到 getDepth(1)

   • 1有左右子树 → 返回1 + min(2, 1) = 2

为什么结果是2？

最小深度是从根节点到最近的叶子节点的最短路径：

• 路径1：1 → 3（长度2）
• 路径2：1 → 2 → 4（长度3）
• 路径3：1 → 2 → 5 → 6（长度4）

最短路径是1 → 3，长度为2。