题解 | #二叉树的最小深度#

考虑类似于最大深度的求法，即使用递归。

1. 到达叶子节点，即左右节点都为null，返回 0(较小的深度，但两边都是0) + 1；
2. 节点的左右子树都不为null，返回左右子树较小的深度 + 1；
3. 节点的左右子树只有一方为null时，求法有所不同，要返回的应该是左右子树深度较大的 + 1，而不是较小的。(因为当节点的左右子树只有一方为null时，返回较小的左右子树深度 + 1，会是0 + 1，但当前节点并非叶子节点，不该 从此处开始 计算最小深度，直接返回0 + 1，会导致上一层的以及最终的深度求解 错误。)

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整型
     */
    public int run (TreeNode root) {     
        if (root == null) {
            return 0;
        }
        /* 1. 广度优先
        // 最小深度，考虑广度优先，找到第一个叶子节点出现的层数
        int result = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            result++;
            while (size-- != 0) {
                TreeNode node = queue.poll();
                if (node.left == null && node.right == null) {
                    return result;
                }
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            
        }
        return result; 
        */ 
        
        // 2. 递归
        return minDepth(root);
    }

    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // 如果左右都为null，即到达叶子节点，返回1，即较小的（都是0） + 1
        if (root.left == null && root.right == null) {
            return 1;
        }
        // 如果左右子树只有一个为null，就要返回二者之中深度较大的 + 1
        if (root.left == null || root.right == null) {
            return Math.max(minDepth(root.left), minDepth(root.right)) + 1;
        }
        // 如果都不为null，就返回较小的 + 1
        return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
    }
}