二叉树的最小深度
难度:
标签:
题目描述
给定一个二叉树,找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明:叶子节点是指没有子节点的节点。
示例 1:
输入:root = [3,9,20,null,null,15,7] 输出:2
示例 2:
输入:root = [2,null,3,null,4,null,5,null,6] 输出:5
提示:
- 树中节点数的范围在
[0, 105]
内 -1000 <= Node.val <= 1000
代码结果
运行时间: 480 ms, 内存: 51.7 MB
/**
* Given a binary tree, find its minimum depth using Java Streams.
* The approach is similar to the non-stream approach but leverages streams for clarity and conciseness.
*
* Approach:
* 1. If the root is null, return 0.
* 2. If the root has no left child, return the minimum depth of the right subtree plus one.
* 3. If the root has no right child, return the minimum depth of the left subtree plus one.
* 4. Use streams to determine the minimum depth of the left and right subtrees.
*/
import java.util.stream.Stream;
public class Solution {
public int minDepth(TreeNode root) {
if (root == null) return 0;
return Stream.of(root.left, root.right)
.mapToInt(child -> child == null ? Integer.MAX_VALUE : minDepth(child))
.min().getAsInt() + 1;
}
}
解释
方法:
该题解使用广度优先搜索(BFS)的方法来解决二叉树的最小深度问题。具体思路如下:
1. 如果根节点为空,直接返回深度0。
2. 创建一个队列,并将根节点加入队列。
3. 初始化深度为1。
4. 当队列不为空时,进行以下操作:
a. 获取当前队列的大小,表示当前层的节点数。
b. 遍历当前层的所有节点:
- 从队列中取出节点。
- 如果该节点是叶子节点(左右子节点都为空),则返回当前深度。
- 如果该节点有左子节点,将左子节点加入队列。
- 如果该节点有右子节点,将右子节点加入队列。
c. 深度加1,继续下一层的遍历。
时间复杂度:
O(n)
空间复杂度:
O(w)
代码细节讲解
🦆
在BFS中,你是如何保证只返回到最近叶子节点的深度而不是其他路径的深度?
▷🦆
为什么选择使用广度优先搜索(BFS)而不是深度优先搜索(DFS)来解决这个问题?
▷🦆
在最坏情况下,队列中最多可能包含多少节点?这种情况是在什么样的树结构下发生的?
▷🦆
为什么在节点出队后立即检查它是否是叶子节点?是否有可能在将子节点加入队列之前进行检查?
▷