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

本文主要是介绍LeetCode力扣题目111:多种算法对比实现二叉树的最小深度，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

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

示例

示例

输入：

    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 = valself.left = leftself.right = rightdef minDepth(root):"""计算二叉树的最小深度:param root: TreeNode, 二叉树的根节点:return: int, 最小深度"""if not root:return 0left = minDepth(root.left)right = minDepth(root.right)# 如果左或右子树为空，应返回非空子树的深度if not root.left or not root.right:return max(left, right) + 1return 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 = valself.left = leftself.right = rightdef 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) + 1if not root:return 0return depth(root)

算法分析

• 时间复杂度：通过缓存优化后，每个节点最多被计算一次，因此时间复杂度为 (O(n))。
• 空间复杂度：因为增加了缓存，所以空间复杂度可能稍高，但在最坏情况下仍然为 (O(h))，其中 (h) 是树的高度，对应于递归栈的最大深度。

优劣势比较

• 优点：
  • 减少了不必要的计算，提高了效率。
  • 通过缓存机制，避免了重复计算相同节点的深度。
• 缺点：
  • 代码复杂度略有增加，需要理解缓存机制。
  • 空间开销可能略大，因为要存储每个节点的计算结果。

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

方法二：迭代广度优先搜索（BFS）

解题步骤

1. 使用队列：利用队列存储每层的节点及其深度。
2. 层级遍历：遍历每个节点，如果是叶子节点，直接返回其深度。
3. 更新队列：将节点的子节点入队。

Python 示例

from collections import dequedef minDepth(root):if not root:return 0queue = deque([(root, 1)])  # 存储节点及其深度while queue:node, depth = queue.popleft()if not node.left and not node.right:return depthif 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 dequeclass TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef minDepth(root):if not root:return 0queue = deque([root])depth = 0  # 初始化深度为0while queue:depth += 1  # 开始新的一层，深度加1for _ in range(len(queue)):  # 遍历当前层的所有节点node = queue.popleft()if not node.left and not node.right:  # 找到第一个叶子节点return depthif node.left:queue.append(node.left)if node.right:queue.append(node.right)return depth  # 在所有节点都有子节点的情况下返回最终深度

算法分析

• 时间复杂度：在最坏情况下，即遍历到最后一层才找到叶子节点，时间复杂度仍为 (O(n))。
• 空间复杂度：空间复杂度主要取决于队列中存储的节点数，最坏情况下，队列中可能包含 (n/2) 个节点（最后一层的节点数），因此空间复杂度为 (O(n))。

优劣势比较

• 优点：
  • 立即找到叶子节点后就结束，避免了不必要的计算。
  • 不需要额外存储节点深度，简化了代码。
• 缺点：
  • 在极端情况下（例如，当树高度非常大时），空间复杂度可能仍然较高。

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

应用示例

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

这篇关于LeetCode力扣题目111:多种算法对比实现二叉树的最小深度的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---