leetcod111.二叉树的最小深度

**二叉树的最小深度**

二叉树是一种常见的数据结构，具有左右孩子的每个结点都只有一个父结点。二叉树的最小深度是指从根结点到叶子结点的最短路径长度。

在 LeetCode 上，有一道题目要求我们实现一个函数 `minDepth`，该函数接收一个二叉树的根结点作为输入，并返回其最小深度。这个问题看起来很简单，但实际上需要一些技巧来解决。

**定义和约束**

假设我们有一个二叉树结构，如下所示：

3 / 
920 / 
157

class TreeNode:
 def __init__(self, x):
 self.val = x self.left = None self.right = Nonedef minDepth(root):
 """
 :type root: TreeNode :rtype: int """
 # 如果二叉树为空，则其最小深度为0。
 if not root:
 return0 # 如果二叉树只有一个结点（即根结点），则其最小深度为1。
 if not root.left and not root.right:
 return1 # 如果二叉树有多个结点，我们可以分别递归地计算左右子树的最小深度，然后返回较小的一个。
 left_depth = minDepth(root.left)
 right_depth = minDepth(root.right)
 # 返回较小的一个。
 return min(left_depth, right_depth) +1

# 创建一个根结点。
root = TreeNode(3)

# 创建左右孩子。
root.left = TreeNode(9)
root.right = TreeNode(20)

# 创建左子树的孩子。
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)

# 计算最小深度。
print(minDepth(root)) # 输出：2