使用深度优先解决“二叉树的最小深度”问题

二叉树的最小深度
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：2
示例 2：
输入：root = [2,null,3,null,4,null,5,null,6]
输出：5

解法一：深度优先
遍历整棵树，找到每一个叶子节点，从叶子节点往上开始计算（使用递归），左右子节点都为空则记录深度为1；左右子节点只有一边，深度记录为子节点深度+1；左右两边都有子节点，则记录左右子节点的深度较小值+1。深度优先与广度优先的区别是深度优先把叶子节点的深度标记为1，广度优先把根节点的深度标记为1。深度优先从下往上遍历，广度优先从上往下遍历。
时间复杂度：O(N)
空间复杂度：O(logN) 取决于树的高度

package od1;

/**
 * 二叉树的最小深度（深度优先）
 * 给定一个二叉树，找出其最小深度，求最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
 * 原文地址：https://www.codernav.com/2843.html
 * 更多算法详解：https://www.codernav.com
 */
public class OdTest31 {
    public static void main(String[] args) {
        TreeNode node7 = new TreeNode(7, null, null);
        TreeNode node6 = new TreeNode(6, node7, null);
        TreeNode node5 = new TreeNode(5, null, null);
        TreeNode node4 = new TreeNode(4, null, null);
        TreeNode node3 = new TreeNode(3, node6, null);
        TreeNode node2 = new TreeNode(2, node4, node5);
        TreeNode node1 = new TreeNode(1, node2, node3);
        // 递归 深度优先
        System.out.println(f(node1));
    }

    public static int f(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // 1.判断是否为子节点，子节点的深度为1
        if (root.left == null && root.right == null) {
            return 1;
        }
        // 最小深度 设置为一个最大值（重要）
        int min = Integer.MAX_VALUE;
        if (root.left != null) {
            min = Math.min(f(root.left), min);
        }
        if (root.right != null) {
            min = Math.min(f(root.right), min);
        }
        // 深度+1
        return min + 1;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    // 深度（广度优先维护深度新增字段）
    int deep;

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}