Java 题解 | #牛群的最短路径#

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return int整型
     */
    private int minDepth = Integer.MAX_VALUE;

    public void dfs(TreeNode root, int depth) {
        if (root.left == null && root.right == null) {
            minDepth = Math.min(minDepth, depth);
            return;
        }
        if (root.left != null) {
            dfs(root.left, depth + 1);
        }
        if (root.right != null) {
            dfs(root.right, depth + 1);
        }
    }

    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        dfs(root, 1);
        return minDepth;
    }
}

该题考察的主要知识点有：

1. 二叉树（Binary Tree）：二叉树是一种特殊的树结构，其中每个节点最多有两个子节点。二叉树可以为空树（没有节点），也可以是非空树，其中一个节点作为根节点，其余节点分别形成根节点的左子树和右子树。
2. 深度优先搜索（Depth First Search，DFS）：深度优先搜索是一种遍历或搜索树或图的算法。在深度优先搜索中，从起始节点开始，沿着路径尽可能深入树或图，直到达到叶子节点或无法继续前进的节点，然后回溯到前一个节点，继续探索其他路径。
3. 最小深度（Minimum Depth）：指从根节点到最近的叶子节点的最短路径上的节点数量。注意，这里的最小深度定义并不是树的高度，因为它要求的是从根节点到叶子节点的路径上的节点数量。

代码的解释大纲如下：

1. 创建一个全局变量 minDepth，用于保存计算得到的最小深度，默认值为最大整数值。
2. 定义一个深度优先搜索的函数 dfs，传入当前节点 root 和当前的深度 depth。
3. 如果当前节点既没有左子节点也没有右子节点，说明当前节点是叶子节点，更新 minDepth 为当前深度和 minDepth 中的较小值，并返回。
4. 如果当前节点有左子节点，则递归调用 dfs 函数，传入左子节点和深度增加1后的值。
5. 如果当前节点有右子节点，则递归调用 dfs 函数，传入右子节点和深度增加1后的值。
6. 定义最小深度的函数 minDepth，传入根节点 root。
7. 判断根节点是否为空，如果为空，则返回0作为最小深度。
8. 调用深度优先搜索的函数 dfs，传入根节点和初始深度1。
9. 返回最小深度 minDepth 作为结果。