111.二叉树的最小深度

class Solution(object): def minDepth(self, root): """ :type root: Optional[TreeNode] :rtype: int """ #层序遍历 # min_depth = 1 # if not root: # return 0 # queue = collections.deque([root]) # while queue: # size = len(queue) # for i in range(size): # node = queue.popleft() # if (not node.left) and (not node.right): # return min_depth # if node.left: # queue.append(node.left) # if node.right: # queue.append(node.right) # min_depth += 1 # return min_depth if not root: return 0 if not root.left and not root.right: return 1 min_depth = 10**9 if root.left: min_depth=min(min_depth,self.minDepth(root.left)) if root.right: min_depth=min(min_depth,self.minDepth(root.right)) return 1+min_depth 解决思路：

我们可以通过 递归 来计算二叉树的最小深度。每次递归的过程是计算左右子树的最小深度，然后返回当前节点的最小深度。

递归的核心： 如果节点为空，返回深度 0。如果当前节点是叶子节点（即左右子树都为空），返回 1。否则，递归计算左右子树的最小深度，并返回 1 + min(左子树深度, 右子树深度)。 Python 代码实现： class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right class Solution: def minDepth(self, root): if not root: # 如果树为空，深度是 0 return 0 # 如果左子树为空，递归计算右子树的深度 if not root.left: return 1 + self.minDepth(root.right) # 如果右子树为空，递归计算左子树的深度 if not root.right: return 1 + self.minDepth(root.left) # 左右子树都不为空，返回左右子树最小深度加 1 left_depth = self.minDepth(root.left) right_depth = self.minDepth(root.right) return 1 + min(left_depth, right_depth) 解释：

基本情况：

如果树为空（root 是 None），返回深度 0。

处理子树为空的情况：

如果当前节点的左子树为空，递归地计算右子树的最小深度。如果当前节点的右子树为空，递归地计算左子树的最小深度。

递归计算左、右子树的最小深度：

如果左右子树都不为空，我们递归计算左右子树的最小深度，返回 1 + min(左子树深度, 右子树深度)。 示例：

我们来看一个具体的例子：

1 / \ 2 3 / 4

在这个例子中：

根节点是 1。左子树的深度是 2（从 1 -> 2 -> 4）。右子树的深度是 1（从 1 -> 3）。

所以，最小深度是 2（路径：1 -> 3）。

具体执行过程：

让我们通过递归一步步执行这个代码。

调用 minDepth(1)：

root 是节点 1，左子树不为空，右子树不为空。递归计算左子树 minDepth(2) 和右子树 minDepth(3)。

调用 minDepth(2)：

root 是节点 2，左子树不为空，右子树为空。计算 minDepth(4)。

调用 minDepth(4)：

root 是节点 4，左子树和右子树都为空。返回深度 1。

返回到 minDepth(2)：

左子树的深度是 1（minDepth(4) 返回 1），右子树为空，返回 1 + 1 = 2。

调用 minDepth(3)：

root 是节点 3，左右子树都为空。返回深度 1。

返回到 minDepth(1)：

左子树的深度是 2，右子树的深度是 1。返回 1 + min(2, 1) = 2。

最终结果是 2。

复杂度分析： 时间复杂度：O(n)，其中 n 是二叉树中的节点数。每个节点会被访问一次。空间复杂度：O(h)，其中 h 是树的高度。递归调用栈的深度是树的高度，最坏情况下树是链状的，递归栈的深度为 n，最好情况下树是平衡的，递归栈的深度为 log(n)。 总结： 递归的核心思想是逐步计算左右子树的最小深度，然后取最小值加 1。处理树为空和只有一个子树的特殊情况。最终得到从根节点到最近叶子节点的最短路径。