111. 二叉树的最小深度

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

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

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

示例 1：

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

示例 2：

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

提示：

• 树中节点数的范围在 $[0,10^5]$内
• $-1000\le Node.val\le 1000$

解法一(BFS+队列)

思路分析：

1. 依旧对二叉树进行层序遍历，在遍历的过程中，对结点进行判断，第一个出现的叶子节点即为离根节点最近的叶子节点

实现代码如下：

class Solution {public int minDepth(TreeNode root) {int ans = 0;if (root == null)return ans;Queue<TreeNode> queue = new ArrayDeque<>();queue.offer(root);while (!queue.isEmpty()) {int size = queue.size();++ ans;    // 记录距离for (int i = 0; i < size; ++ i) {TreeNode node = queue.poll();if (node.left == null && node.right == null) {// 找到最近的叶子节点return ans;}if (node.left != null) queue.offer(node.left);if (node.right != null) queue.offer(node.right);}}return ans;}
}

提交结果如下：

解答成功:
执行耗时:2 ms,击败了86.64% 的Java用户
内存消耗:61.6 MB,击败了6.25% 的Java用户

复杂度分析：

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$，辅助队列

解法二(前序求深度递归)

思路分析：

1. 使用递归来寻找离根节点最近的叶子节点

2. 思考递归参数，即需要传递二叉树的节点和节点所在层数，且不需要返回值

3. 对于递归边界条件，即当节点为空时，不需要往下遍历，同时当遍历到叶子节点时，比较是否为最短距离，并结束递归

4. 递归过程则是，对叶子节点距离根节点的距离作比较，寻找最小距离

实现代码如下：

class Solution {int ans = Integer.MAX_VALUE;public int minDepth(TreeNode root) {getMinDepth(root, 1);if (ans == Integer.MAX_VALUE) return 0;return ans;}private void getMinDepth(TreeNode node, int depth) {if (node == null)return ;    // 结束遍历if (node.left == null && node.right == null) {ans = Math.min(depth, ans);        // 记录最小深度return ;}getMinDepth(node.left, depth+1);getMinDepth(node.right, depth+1);}
}

提交结果如下：

解答成功:
执行耗时:7 ms,击败了63.76% 的Java用户
内存消耗:62 MB,击败了5.02% 的Java用户

复杂度分析：

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

解法三(后序求高度递归)

思路分析：

1. 对于该题求二叉树的最小深度，即等同于求二叉树根节点到最近叶子节点的高度，因此可以通过后序遍历来求二叉树根节点到最近叶子节点的高度

2. 首先对递归的参数和返回值进行考虑，因为需要遍历二叉树，所以递归传递参数为二叉树节点，同时需要求高度，所以递归函数返回值为int型

3. 然后思考递归的边界条件，因为从叶子节点返回得到高度，所以对于空节点则直接返回0

4. 对于递归的过程，则按照后序遍历，先遍历左右子树，然后进行判断得到当前节点的最小高度

   1. 若左子树为null，则返回右子树高度+1

   2. 若右子树为null，则返回左子树高度+1

   3. 若左右子树均不为null，则返回左右子树最小高度+1

实现代码如下：

class Solution {public int minDepth(TreeNode root) {return getHeight(root);}// 后序遍历递归求二叉树节点高度private int getHeight(TreeNode node) {if (node == null)return 0;    // 边界条件 空节点返回0// 左int leftHeight = getHeight(node.left);// 右int rightHeight = getHeight(node.right);// 获取中 高度int height;if (node.left != null && node.right == null)height = leftHeight+1;else if (node.left == null && node.right != null)height = rightHeight+1;else height = Math.min(leftHeight, rightHeight)+1;return height;}
}

提交结果如下：

解答成功:
执行耗时:9 ms,击败了37.82% 的Java用户
内存消耗:61.7 MB,击败了7.75% 的Java用户

复杂度分析：

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$