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;
    }
}

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

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

代码的解释大纲如下：

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