题目描述
给定一个二叉树,找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明: 叶子节点是指没有子节点的节点。
示例:
给定二叉树 [3,9,20,null,null,15,7]
返回它的最小深度 2.
解法
注意:一定要到达叶节点!
1. DFS
思路:使用深度优先搜索遍历树,递归返回最小的深度。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
|
class Solution { public int minDepth(TreeNode root) { if (root == null) return 0; if (root.left == null && root.right == null) return 1; int depth = Integer.MAX_VALUE; if (root.left != null) { depth = Math.min(minDepth(root.left), depth); } if (root.right != null) { depth = Math.min(minDepth(root.right), depth); } return depth + 1; } }
|
时间复杂度为$O(n)$ 树的节点数
空间复杂度为$O(H)$ 递归栈空间大小为树的深度,一般情况下$logn$,最坏为$N$
2. BFS
思路:使用广度优先搜索遍历树,由于是一层一层进行遍历,这时如果发现叶节点则一定保证是最小深度,直接返回深度即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
|
import java.util.Queue; import java.util.LinkedList; class Solution { public int minDepth(TreeNode root) { if (root == null) return 0; Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); int count; TreeNode node; int depth = 0; while (!queue.isEmpty()) { count = queue.size(); for (int i = 0; i < count; i++) { node = queue.poll(); if (node.left == null && node.right == null) return depth + 1; if (node.left != null) queue.offer(node.left); if (node.right != null) queue.offer(node.right); } depth++; } return depth; } }
|
时间复杂度为$O(n)$ 树的节点数
空间复杂度为$O(n)$ 队列空间大小为树的节点数,最坏为$n$
3. 不知道名字法。。
思路:这是我一开始看到题目的思路,有点动态规划的味道🤔一个树的最小深度必然由其左右子树的最小深度得来,状态转移方程为$dp[i] = min(dp[left] + dp[right]) + 1$,所以我开始的代码是这样的
1 2 3 4 5 6 7 8
| class Solution { public int minDepth(TreeNode root) { if (root == null) return 0; int depthLeft = minDepth(root.left); int depthRight = minDepth(root.right); return Math.min(depthLeft, depthRight) + 1; } }
|
结果是没有考虑到这种情况,按照我上面的代码,1的右子树为null,返回的值为0,比左子树的深度1小,所以返回 0 + 1 = 1,而深度是必须要到达叶节点的,所以这种情况的正确值是2.
然后我以为我的想法是错的😢,就使用DFS和BFS去做了。结果在评论中发现一个相同思路的!只要将这种情况拎出来单独判断即可~
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
|
class Solution { public int minDepth(TreeNode root) { if (root == null) return 0; int depthLeft = minDepth(root.left); int depthRight = minDepth(root.right); if (root.left == null || root.right == null) return Math.max(depthLeft, depthRight) + 1; return Math.min(depthLeft, depthRight) + 1; } }
|
和使用DFS的复杂度相同
时间复杂度为$O(n)$ 树的节点数
空间复杂度为$O(H)$ 递归栈空间大小为树的深度,一般情况下$logn$,最坏为$N$
参考