Day24 - 104.二叉树的最小深度

题目链接：https://leetcode.cn/problems/minimum-depth-of-binary-tree/

1. 问题理解

题目要找的是 最小深度，意思是：

• 从 根节点 出发，到 最近的叶子节点（左右孩子都为 None）的路径上，节点数量最少的那条路径的节点数。

• 注意：必须到达叶子节点，不能只是到某个空节点就停。

• 叶子节点定义：左右子节点都为空的节点。

2. 核心算法 —— 递归（DFS）

思路：

1. 如果节点为空（None），深度是 0（递归终止条件）。

2. 递归求左子树的最小深度 → leftDepth

3. 递归求右子树的最小深度 → rightDepth

4. 关键点：

   • 如果 左子树为空，但右子树不为空 → 最小深度必须走右子树

   • 如果 右子树为空，但左子树不为空 → 最小深度必须走左子树

   • 否则（左右都不为空） → 最小深度 = 1 + min(leftDepth, rightDepth)

def getDepth(self,node):
        if node is None:
            return 0
        leftdepth = self.getDepth(node.left)
        rightdepth = self.getDepth(node.right)
        
        if node.left is not None and node.right is None:
            return 1+ rightdepth
        if node.right is not None and node.left is None:
            return 1+ leftdepth
        result = 1 + min(leftdepth,rightdepth)
        return result

3. 关键点和边界条件

• 终止条件：

  • 节点为空，返回 0

  • 节点为叶子节点，返回 1（会在 min(...) 情况中自然计算出来）

• 左右子树一边为空的情况：

  • 不能直接取 min(leftDepth, rightDepth)，否则会因为空节点返回 0 而导致错误结果

  • 必须跳过空的一边，去计算不为空的一边

• 空树：返回 0

• 只有一个节点的树：返回 1

• 时间复杂度：O(n)（每个节点访问一次）

• 空间复杂度：O(h)，h 为树的高度（递归栈）

完整代码：

class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        return self.getDepth(root)
    def getDepth(self,node):
        if node is None:
            return 0
        leftdepth = self.getDepth(node.left)
        rightdepth = self.getDepth(node.right)
        
        if node.left is not None and node.right is None:
            return 1+ rightdepth
        if node.right is not None and node.left is None:
            return 1+ leftdepth
        result = 1 + min(leftdepth,rightdepth)
        return result