# 二叉树最小深度

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

** 说明：** 叶子节点是指没有子节点的节点。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：2

示例 2：

输入：root = [2,null,3,null,4,null,5,null,6]
输出：5

提示：

如果已经学习过二叉树最大深度的话你可能会想到这样写，如下代码：

	public int minDepth(TreeNode root) {
	if(root == null) return 0;
	int d1 = minDepth(root.left);
	int d2 = minDepth(root.right);
	return Math.min(d1, d2) + 1;
	}

但是，这样写是错误的！

运行结果：

下面分析为什么这样写是错误的。

分析执行过程

深度 2
  1
 /
2

我们根据上面的例子来讲首先它的根节点是 1

	public int minDepth(TreeNode root) {
	// 传进来根节点为 1 条件不成立
	if(root == null) return 0;
	// 求根节点开始的左子树深度
	int d1 = minDepth(root.left);// 求出来的应该是 1
	// 求根节点卡开始的右子树深度
	int d2 = minDepth(root.right);// 求出来应该是 0
	// 从 0 和 1 挑选出一个最小值也就是 0 然后 + 1 返回，所以就得出了根节点它的深度是 1
	return Math.min(d1, d2) + 1;
	}

通过上面分析可以得出这样的结果就不对了，它的深度应该是 2 才对

问题就出在：它有一个子树是 null 的时候，我们应该不把它计算在内的

对应下面的例子来看

我们看左边不为 null 的子树才是它的深度，右边为 null 的我们不应该把它作为深度的比较

深度 2
  1
 /
2

因此我们需要在左右子树返回了以后做一些判断

# 代码：

	class Solution {
	public int minDepth(TreeNode root) {
	if(root == null) return 0;
	int d1 = minDepth(root.left);
	int d2 = minDepth(root.right);
	if(d2 == 0) return d1 + 1;
	if(d1 == 0) return d2 + 1;
	return Math.min(d1, d2) + 1;
	}
	}

提交结果：