leetcode
leetcode 101 ~ 150
二叉树的最小深度

二叉树的最小深度

难度:

标签:

题目描述

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

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

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

 

示例 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中,我通过层序遍历来确保总是首先到达最近的叶子节点。因为BFS是按层(从根节点到叶子节点)进行的,所以确保了一旦遇到任何叶子节点,它必定是最近的叶子节点,因此可以立即返回其深度。
🦆
为什么选择使用广度优先搜索(BFS)而不是深度优先搜索(DFS)来解决这个问题?
选择BFS的原因是它更适合于寻找最小深度。在使用DFS时,我们可能会首先深入到树的一个深层分支,而这个分支可能不包含最近的叶子节点。而BFS从根节点开始逐层向下搜索,一旦找到叶子节点,就可以确保这是到达叶子节点的最短路径。
🦆
在最坏情况下,队列中最多可能包含多少节点?这种情况是在什么样的树结构下发生的?
在最坏情况下,队列中可能会包含与二叉树的最宽层一样多的节点。这种情况通常发生在每个节点都有两个子节点的完全二叉树中。例如,在完全二叉树的最后一层,如果树高为h,最后一层可能包含2^(h-1)个节点。
🦆
为什么在节点出队后立即检查它是否是叶子节点?是否有可能在将子节点加入队列之前进行检查?
在节点出队后立即检查它是否是叶子节点可以避免不必要的操作,因为一旦确定一个节点是叶子节点,我们就可以返回其深度,不需要进一步探索其子节点。在将子节点加入队列前进行检查是不合适的,因为我们需要首先确认当前节点是否为叶子节点;如果不是,我们才需要考虑其子节点。

相关问题

二叉树的层序遍历

给你二叉树的根节点 root ,返回其节点值的 层序遍历 。 (即逐层地,从左到右访问所有节点)。

 

示例 1:

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

示例 2:

输入:root = [1]
输出:[[1]]

示例 3:

输入:root = []
输出:[]

 

提示:

  • 树中节点数目在范围 [0, 2000]
  • -1000 <= Node.val <= 1000

二叉树的最大深度

给定一个二叉树 root ,返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

 

示例 1:

 

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

示例 2:

输入:root = [1,null,2]
输出:2

 

提示:

  • 树中节点的数量在 [0, 104] 区间内。
  • -100 <= Node.val <= 100