这是悦乐书的第168次更新，第170篇原创
01 看题和准备
今天介绍的是LeetCode算法题中Easy级别的第27题（顺位题号是111）。给定二叉树，找到它的最小深度。最小深度是沿从根节点到最近的叶节点的最短路径上的节点数。叶子节点是没有子节点的节点。例如：
给定二叉树[3,9,20，null，null，15,7]，
3
/ \
9 20
/ \
15 7
返回其最小深度= 2。
本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。
02 第一种解法
之前我们有解过最大深度的题，今天这道题相反，求最短路径，那是不是直接将原来代码中的最大改为最小即可？如果你这样试过，会发现根本不是那么回事！
特殊情况一：当传入的二叉树为空时，最短路径就是0。
特殊情况二：当传入的二叉树只有根节点时，最短路径是1.
正常情况：当某一节点的左子节点为空时，这时我们需要求其右子节点的最短路径；当某一节点的右子节点为空时，这时我们需要求其左子节点的最短路径；当某一节点的左子节点和右子节点都不为空时，这时我们要求其左子树和右子树的最短路径。
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
if ((root.left == null) && (root.right == null)) {
return 1;
}
if (root.left == null) {
return minDepth(root.right) + 1;
}
if (root.right == null) {
return minDepth(root.left) + 1;
}
return 1+Math.min(minDepth(root.left), minDepth(root.right));
}
03 第二种解法
除了上面的递归外，我们依旧可以使用遍历的方法。此解法与求最大深度时的第三种解法类似，也是利用队列，只是多了一步判断：当左右节点都为空时，此节点是叶子节点，需要更新最短路径的值。
public int minDepth2(TreeNode root) {
if (root == null) {
return 0;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int minDepth = Integer.MAX_VALUE;
int depth = 1;
while (!queue.isEmpty()) {
int size = queue.size();
while (size > 0) {
TreeNode t = queue.poll();
if (t.left != null) {
queue.offer(t.left);
}
if (t.right != null) {
queue.offer(t.right);
}
if (t.left == null && t.right == null) {
minDepth = Math.min(minDepth, depth);
}
size--;
}
depth++;
}
return minDepth;
}
04 小结
以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！