小编点评

```python class TreeNode: def __init__(self, val): self.val = val self.left = None self.right = None def minDepth(root): # If the root is null, return 0 if root is None: return 0 # Calculate the depth of the root node depth = 0 # If the left and right nodes are both null, return the depth of the root node if root.left is None and root.right is None: return depth # If the left node is null, calculate the depth of the right node and add 1 elif root.left is None: depth = depth + 1 return depth + minDepth(root.right) # If the right node is null, calculate the depth of the left node and add 1 elif root.right is None: depth = depth + 1 return depth + minDepth(root.left) # Return the minimum depth among the left and right subtrees return min(depth + minDepth(root.left), depth + minDepth(root.right)) ``` **Explanation:** 1. The `minDepth` function takes a TreeNode `root` as input. 2. It initializes `depth` to 0. This will store the minimum depth found among all possible paths from the root to the leaves. 3. If the `root` is `None`, it returns 0, indicating that the minimum depth is reached when the tree is empty. 4. If the `left` and `right` nodes are both `None`, it returns the depth of the root node, as it is the shortest path from the root to any leaf. 5. If the `left` node is `None`, it recursively calculates the minimum depth of the right subtree and adds 1 to it. 6. Similarly, if the `right` node is `None`, it recursively calculates the minimum depth of the left subtree and adds 1 to it. 7. The function chooses the minimum of the left and right subtree depths and returns it as the minimum depth. 8. The function uses a `depth + minDepth` approach to calculate the minimum depth, where `depth` represents the current depth from the root to the current node, and `minDepth` represents the minimum depth from the root to the leaves. 9. The function continues this process recursively until it reaches the leaves and returns the minimum depth it finds.

正文

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明：叶子节点是指没有子节点的节点。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：2
示例 2：

输入：root = [2,null,3,null,4,null,5,null,6]
输出：5

解题思路

1. 如果当前节点为null， 返回0
2. 判断左节点的最小路径，和右节点的最小路径，然后取最小值，即为当前节点的最小深度
3. 递归思想，从下到上，依次累加最小路径值，得到的值即为最小路径

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int minDepth(TreeNode root) {
        int depth = 0;
        if (root == null) {
            return depth;
        }
        depth += 1;
        if (root.left == null && root.right == null) {
            return depth;
        }
        if (root.left == null) {
            return depth + minDepth(root.right);
        } 
        if (root.right == null) {
            return depth + minDepth(root.left);
        }

        int leftDepth = depth + minDepth(root.left);
        int rightDepth = depth + minDepth(root.right);
        return leftDepth > rightDepth ? rightDepth : leftDepth;
    }
}