package binarytree.minDepth;
import binarytree.untils.TreeNode;
/**
 * 给定一个二叉树，找出其最小深度。
 * <p>
 * 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
 * <p>
 * 说明：叶子节点是指没有子节点的节点。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * <p>
 * 输入：root = [3,9,20,null,null,15,7]
 * 输出：2
 * 示例 2：
 * <p>
 * 输入：root = [2,null,3,null,4,null,5,null,6]
 * 输出：5
 * <p>
 * <p>
 * 提示：
 * <p>
 * 树中节点数的范围在 [0, 105] 内
 * -1000 <= Node.val <= 1000
 * 通过次数300,383提交次数612,629
 */
public class minDepth {
    /**
     * 公式 ：分三种情况 1：无节点 2，有根 无叶子节点 3有至少一个左右节点
     * 递归终止条件 1情况 return 0，2情况 return 1 3情况 就要一直进行向下遍历，累加 左右节点的深度，返回他们的和，
     *
     * @param root
     * @return
     */
    public static int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        int l = minDepth(root.left);
        int r = minDepth(root.right);
        if (root.left == null || root.right == null) {
            return  l+r+1;
        }
        return Math.min(l,r)+1;
    }
}