作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、python
欢迎加入社区：码上找工作
作者专栏每日更新：
题目描述
给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。注意：叶子节点是指没有子节点的节点。
示例
示例
输入：
3 / \ 9 20 / \ 15 7
输出：2 （根节点到节点 9 的路径最短）
方法一：递归深度优先搜索（DFS）
解题步骤
- 递归终止条件：如果当前节点为空，则返回无穷大（表示没有子节点）。
- 递归左右子树：计算左子树和右子树的最小深度。
- 计算当前节点的最小深度：当前节点的最小深度为左右子树的最小深度加一。
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
改进点
- 提前终止：在发现当前节点的一个子树深度已经小于另一个子树时，可以提前终止对该较深子树的深度计算。这样做可以减少不必要的递归调用。
- 缓存结果：对于每个节点的左右子树深度，可以使用哈希表或数组缓存其结果，避免重复计算。
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）
解题步骤
- 使用队列：利用队列存储每层的节点及其深度。
- 层级遍历：遍历每个节点，如果是叶子节点，直接返回其深度。
- 更新队列：将节点的子节点入队。
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
改进点
- 避免使用额外的深度存储：在当前的实现中，每个节点及其对应的深度都存储在队列中。我们可以优化这一点，通过在每一轮循环开始时记录队列的长度，从而避免存储每个节点的深度。
- 更早的终止条件：在找到第一个叶子节点后，可以立即退出循环，而不是等待当前层的所有节点都被检查完。
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 方法更加高效和直观，尤其是在处理大型数据集时，这种方法能快速找到最小深度，而无需深入遍历树的所有部分。这使得它在实际应用中更加实用，尤其是在数据结构动态变化较大的环境中。
应用示例
这些方法在需要快速确定数据结构（如游戏、网络路由、社交网络的层级结构）中的最小路径或深度时非常有用。
欢迎关注微信公众号 数据分析螺丝钉
