LeetCode力扣题目111:多种算法对比实现二叉树的最小深度

简介: LeetCode力扣题目111:多种算法对比实现二叉树的最小深度

作者介绍:10年大厂数据\经营分析经验,现任大厂数据部门负责人。

会一些的技术:数据分析、算法、SQL、大数据相关、python

欢迎加入社区:码上找工作

作者专栏每日更新:

LeetCode解锁1000题: 打怪升级之旅

python数据分析可视化:企业实战案例

python源码解读

程序员必备的数学知识与应用

题目描述

给定一个二叉树,找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。注意:叶子节点是指没有子节点的节点。

示例

示例

输入:

3
   / \
  9  20
    /  \
   15   7

输出:2 (根节点到节点 9 的路径最短)

方法一:递归深度优先搜索(DFS)

解题步骤
  1. 递归终止条件:如果当前节点为空,则返回无穷大(表示没有子节点)。
  2. 递归左右子树:计算左子树和右子树的最小深度。
  3. 计算当前节点的最小深度:当前节点的最小深度为左右子树的最小深度加一。
Python 示例
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
def minDepth(root):
    """
    计算二叉树的最小深度
    :param root: TreeNode, 二叉树的根节点
    :return: int, 最小深度
    """
    if not root:
        return 0
    left = minDepth(root.left)
    right = minDepth(root.right)
    # 如果左或右子树为空,应返回非空子树的深度
    if not root.left or not root.right:
        return max(left, right) + 1
    return min(left, right) + 1
算法分析
  • 时间复杂度:(O(n)),每个节点访问一次。
  • 空间复杂度:(O(h)),递归栈的深度,其中 (h) 是树的高度。
    方法一的基本思路是使用深度优先搜索(DFS)递归地检查每个节点的左右子树的最小深度。虽然这种方法直观易懂,但存在重复计算和不必要的深度遍历问题,尤其是在遇到高度不平衡的树时。我们可以通过一些改进来优化这种方法。

方法一改进:优化的DFS

改进点
  1. 提前终止:在发现当前节点的一个子树深度已经小于另一个子树时,可以提前终止对该较深子树的深度计算。这样做可以减少不必要的递归调用。
  2. 缓存结果:对于每个节点的左右子树深度,可以使用哈希表或数组缓存其结果,避免重复计算。
Python 示例
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
def minDepth(root):
    from functools import lru_cache
    
    @lru_cache(None)  # 缓存节点深度计算结果
    def depth(node):
        if not node:
            return float('inf')  # 空节点返回无穷大,表示不可达
        if not node.left and not node.right:
            return 1  # 叶子节点深度为1
        # 使用缓存结果,避免重复计算
        left_depth = depth(node.left)
        right_depth = depth(node.right)
        # 提前终止,如果一个子树深度明显小于另一个,不继续计算较大深度子树
        return min(left_depth, right_depth) + 1
    if not root:
        return 0
    return depth(root)
算法分析
  • 时间复杂度:通过缓存优化后,每个节点最多被计算一次,因此时间复杂度为 (O(n))。
  • 空间复杂度:因为增加了缓存,所以空间复杂度可能稍高,但在最坏情况下仍然为 (O(h)),其中 (h) 是树的高度,对应于递归栈的最大深度。
优劣势比较
  • 优点
  • 减少了不必要的计算,提高了效率。
  • 通过缓存机制,避免了重复计算相同节点的深度。
  • 缺点
  • 代码复杂度略有增加,需要理解缓存机制。
  • 空间开销可能略大,因为要存储每个节点的计算结果。

通过这种改进,DFS 方法不仅变得更加高效,而且也避免了在不平衡树上的性能陷阱。这使得它更加适用于大规模或深度较大的树结构的场景。

方法二:迭代广度优先搜索(BFS)

解题步骤
  1. 使用队列:利用队列存储每层的节点及其深度。
  2. 层级遍历:遍历每个节点,如果是叶子节点,直接返回其深度。
  3. 更新队列:将节点的子节点入队。
Python 示例
from collections import deque
def minDepth(root):
    if not root:
        return 0
    queue = deque([(root, 1)])  # 存储节点及其深度
    while queue:
        node, depth = queue.popleft()
        if not node.left and not node.right:
            return depth
        if node.left:
            queue.append((node.left, depth + 1))
        if node.right:
            queue.append((node.right, depth + 1))
算法分析
  • 时间复杂度:(O(n)),每个节点至多访问一次。
  • 空间复杂度:(O(n)),在最坏的情况下,队列中需要存储所有节点。

方法二使用的是广度优先搜索(BFS)来确定二叉树的最小深度。它通过迭代方式检查每一层的节点,直到找到第一个叶子节点,然后立即返回这个叶子节点的深度。这个方法的主要优点是它不必检查所有的节点,尤其是在一个高度不平衡的树中,它可以更快地找到最浅的叶子节点。尽管如此,我们仍然可以对其进行一些改进,以提高其效率和可用性。

方法二改进:优化的BFS

改进点
  1. 避免使用额外的深度存储:在当前的实现中,每个节点及其对应的深度都存储在队列中。我们可以优化这一点,通过在每一轮循环开始时记录队列的长度,从而避免存储每个节点的深度。
  2. 更早的终止条件:在找到第一个叶子节点后,可以立即退出循环,而不是等待当前层的所有节点都被检查完。
Python 示例
from collections import deque
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
def minDepth(root):
    if not root:
        return 0
    queue = deque([root])
    depth = 0  # 初始化深度为0
    while queue:
        depth += 1  # 开始新的一层,深度加1
        for _ in range(len(queue)):  # 遍历当前层的所有节点
            node = queue.popleft()
            if not node.left and not node.right:  # 找到第一个叶子节点
                return depth
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    return depth  # 在所有节点都有子节点的情况下返回最终深度
算法分析
  • 时间复杂度:在最坏情况下,即遍历到最后一层才找到叶子节点,时间复杂度仍为 (O(n))。
  • 空间复杂度:空间复杂度主要取决于队列中存储的节点数,最坏情况下,队列中可能包含 (n/2) 个节点(最后一层的节点数),因此空间复杂度为 (O(n))。
优劣势比较
  • 优点
  • 立即找到叶子节点后就结束,避免了不必要的计算。
  • 不需要额外存储节点深度,简化了代码。
  • 缺点
  • 在极端情况下(例如,当树高度非常大时),空间复杂度可能仍然较高。

通过这种改进,BFS 方法更加高效和直观,尤其是在处理大型数据集时,这种方法能快速找到最小深度,而无需深入遍历树的所有部分。这使得它在实际应用中更加实用,尤其是在数据结构动态变化较大的环境中。

应用示例

这些方法在需要快速确定数据结构(如游戏、网络路由、社交网络的层级结构)中的最小路径或深度时非常有用。

欢迎关注微信公众号 数据分析螺丝钉


相关文章
|
22天前
|
存储 算法
【数据结构和算法】--- 二叉树(4)--二叉树链式结构的实现(2)
【数据结构和算法】--- 二叉树(4)--二叉树链式结构的实现(2)
15 0
|
22天前
|
存储 算法 Linux
【数据结构和算法】---二叉树(1)--树概念及结构
【数据结构和算法】---二叉树(1)--树概念及结构
15 0
|
13天前
|
算法
刷算法Leetcode---9(二叉树篇Ⅲ)
刷算法Leetcode---9(二叉树篇Ⅲ)
12 3
|
20天前
|
存储 算法 搜索推荐
力扣每日一题 6/13 反悔贪心算法
力扣每日一题 6/13 反悔贪心算法
12 1
|
22天前
|
算法 分布式数据库
【数据结构和算法】--- 二叉树(5)--二叉树OJ题
【数据结构和算法】--- 二叉树(5)--二叉树OJ题
12 1
|
12天前
|
算法 JavaScript
JS 【详解】二叉树(含二叉树的前、中、后序遍历技巧和算法实现)
JS 【详解】二叉树(含二叉树的前、中、后序遍历技巧和算法实现)
18 0
|
22天前
|
算法
【数据结构和算法】--- 二叉树(3)--二叉树链式结构的实现(1)
【数据结构和算法】--- 二叉树(3)--二叉树链式结构的实现(1)
6 0
|
22天前
|
存储 算法
【数据结构和算法】---二叉树(2)--堆的实现和应用
【数据结构和算法】---二叉树(2)--堆的实现和应用
10 0
|
2天前
|
机器学习/深度学习 算法 数据挖掘
基于改进K-means的网络数据聚类算法matlab仿真
**摘要:** K-means聚类算法分析,利用MATLAB2022a进行实现。算法基于最小化误差平方和,优点在于简单快速,适合大数据集,但易受初始值影响。文中探讨了该依赖性并通过实验展示了随机初始值对结果的敏感性。针对传统算法的局限,提出改进版解决孤点影响和K值选择问题。代码中遍历不同K值,计算距离代价,寻找最优聚类数。最终应用改进后的K-means进行聚类分析。
|
4天前
|
算法 数据安全/隐私保护
基于GA遗传优化算法的Okumura-Hata信道参数估计算法matlab仿真
在MATLAB 2022a中应用遗传算法进行无线通信优化,无水印仿真展示了算法性能。遗传算法源于Holland的理论,用于全局优化,常见于参数估计,如Okumura-Hata模型的传播损耗参数。该模型适用于150 MHz至1500 MHz的频段。算法流程包括选择、交叉、变异等步骤。MATLAB代码执行迭代,计算目标值,更新种群,并计算均方根误差(RMSE)以评估拟合质量。最终结果比较了优化前后的RMSE并显示了SNR估计值。
17 7

热门文章

最新文章