alleyf

二叉树最小深度算法解析

🎯 问题描述

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

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

叶子节点指没有子节点的节点。

📊 示例

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

    3
   / \
  9  20
     / \
    15  7

最短路径是 3 → 9，深度为 2。

🏗️ 算法分析

二叉树最小深度问题可以用 深度优先搜索 (DFS) 和 广度优先搜索 (BFS) 两种方式解决。

🎯 DFS 实现

📝 递归解法

递归三部曲：

1. 确定递归函数参数和返回值

   • 参数：二叉树根节点
   • 返回值：最小深度 (int)

2. 基线条件

   • 如果根节点为 null，返回 0

3. 递归规则

   • 如果节点是叶子（无左子和右子），返回 1
   • 如果只有左子，返回 1 + 左子深度
   • 如果只有右子，返回 1 + 右子深度
   • 如果左右子都有，返回 1 + min(左子深度, 右子深度)

注意点：

• 不能简单地使用 Math.min(minDepth(left), minDepth(right)) + 1
• 因为如果一个子树为 null，那个分支会被认为深度为 0，但不是叶子

代码实现：

class Solution:
    def minDepth(self, root: TreeNode) -> int:
        # 基线条件
        if not root:
            return 0
        
        # 如果是叶子节点
        if not root.left and not root.right:
            return 1
        
        # 如果只有左子
        if root.left and not root.right:
            return 1 + self.minDepth(root.left)
        
        # 如果只有右子
        if root.right and not root.left:
            return 1 + self.minDepth(root.right)
        
        # 左右子都存在
        return 1 + min(self.minDepth(root.left), self.minDepth(root.right))

🔄 非递归实现 (DFS)

使用栈来模拟递归过程：

class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        
        stack = [(root, 1)]  # (节点, 当前深度)
        min_depth = float('inf')
        
        while stack:
            node, depth = stack.pop()
            
            # 如果是叶子节点，更新最小深度
            if not node.left and not node.right:
                min_depth = min(min_depth, depth)
            
            # 左右子节点进入栈
            if node.right:
                stack.append((node.right, depth + 1))
            if node.left:
                stack.append((node.left, depth + 1))
        
        return min_depth

🎯 BFS 实现

思路：

• 使用队列进行层次遍历
• 第一个遇到的叶子节点就是最近的叶子，返回其深度
• 这样可以早时终止，不必遍历整棵树

代码实现：

from collections import deque

class Solution:
    def minDepth(self, root: TreeNode) -> int:
        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)

• n 为二叉树的节点数
• 最坏情况下需要遍历所有节点

📈 空间复杂度

方法	空间复杂度
递归 DFS	O(h)
非递归 DFS	O(h)
BFS	O(w)

备注：

• h 为树的高度
• w 为最大帧宽 (width)
• 对于平衡树： h = O(log n), w = O(n)
• 对于垂直树： h = O(n), w = O(1)

🎯 算法选择建议

📈 性能对比

方法	时间复杂度	空间复杂度	特点
递归 DFS	O(n)	O(h)	代码简洁，递归深度超过限时可能引发栈溢出
非递归 DFS	O(n)	O(h)	避免递归栈溢出，代码复杂度增加
BFS	O(n)	O(w)	可能早时终止，但平衡树空间消耗较大

🔧 建议选择

1. 普通树或垂直树：选择递归 DFS
2. 平衡树：可选择 BFS (可能早时终止)
3. 树高度较大：选择非递归 DFS 或 BFS
4. 代码简洁性高：选择递归 DFS

📖 示例解析

📊 示例 1

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

    3
   / \
  9  20
     / \
    15  7

分析：

• 节点 3: 不是叶子，有左右子
• 节点 9: 叶子，深度 = 2
• 节点 20: 不是叶子，有左右子
• 节点 15: 叶子，深度 = 3
• 节点 7: 叶子，深度 = 3

结果：最小深度 = 2

📊 示例 2

输入: [1,2]

    1
   /
  2

分析：

• 节点 1: 不是叶子，只有左子
• 节点 2: 叶子，深度 = 2

结果：最小深度 = 2

🎯 常见陷阱

🔄 陷阱 1：简单的 min 方法

# 错误的实现
return min(self.minDepth(root.left), self.minDepth(root.right)) + 1

问题：

• 如果一个子树为 null，那个分支会返回 0
• 0 不是叶子，但被认为最短路径

🔄 陷阱 2：忽略叶子节点定义

# 错误的实现
if not root.left or not root.right:
    return 1

问题：

• 不是所有无子节点的节点都是叶子
• 只有无左子且无右子的节点才是叶子

📚 算法扩展

🔄 树的最大深度

最大深度的计算相对简单：

def maxDepth(self, root: TreeNode) -> int:
    if not root:
        return 0
    return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

🔄 树的平衡性检查

使用最大深度和最小深度的差值来检查树的平衡性：

def isBalanced(self, root: TreeNode) -> bool:
    def check(node):
        if not node:
            return 0
        
        left = check(node.left)
        if left == -1:
            return -1
        
        right = check(node.right)
        if right == -1:
            return -1
        
        if abs(left - right) > 1:
            return -1
        
        return max(left, right) + 1
    
    return check(root) != -1

📋 总结

二叉树最小深度算法是基础的数据结构算法问题，具有以下特点：

1. 理论基础：使用 DFS 或 BFS 遍历树
2. 关键点：正确定义叶子节点，处理子树为 null 的特殊情况
3. 时间复杂度：所有方法都是 O(n)
4. 空间复杂度：递归方法使用递归栈，非递归方法使用自己的栈或队列
5. 应用场景：基础数据结构训练，深度优先和广度优先算法的实践

掌握了最小深度算法，便能底定地理解更多的二叉树问题。