LeetCode 热题100 104. 二叉树的最大深度

LeetCode 热题100 | 104. 二叉树的最大深度

大家好，今天我们来解决一道经典的算法题——二叉树的最大深度。这道题在 LeetCode 上被标记为简单难度，要求我们给定一个二叉树的根节点 root，返回其最大深度。下面我将详细讲解解题思路，并附上 Python 代码实现。

题目描述

给定一个二叉树 root，返回其最大深度。二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数。

示例：

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

解题思路

二叉树的最大深度可以通过递归或迭代的方式来计算。递归法是最直观的方法，而迭代法通常使用广度优先搜索（BFS）来实现。

核心思想

1. 递归法：

   • 二叉树的深度等于其左右子树的最大深度加 1。
   • 递归地计算左右子树的深度，取最大值并加 1。

2. 迭代法（BFS）：

   • 使用队列进行层次遍历，每遍历一层，深度加 1。

代码实现

方法 1：递归法

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def maxDepth(root):
    """
    :type root: TreeNode
    :rtype: int
    """
    if not root:
        return 0
    # 递归计算左右子树的深度
    left_depth = maxDepth(root.left)
    right_depth = maxDepth(root.right)
    # 返回左右子树的最大深度加 1
    return max(left_depth, right_depth) + 1

方法 2：迭代法（BFS）

from collections import deque

def maxDepth(root):
    """
    :type root: TreeNode
    :rtype: int
    """
    if not root:
        return 0
    
    queue = deque([root])  # 使用队列存储节点
    depth = 0  # 初始化深度
    
    while queue:
        level_size = len(queue)  # 当前层的节点数
        for _ in range(level_size):
            node = queue.popleft()  # 弹出当前节点
            if node.left:
                queue.append(node.left)  # 将左子节点加入队列
            if node.right:
                queue.append(node.right)  # 将右子节点加入队列
        depth += 1  # 遍历完一层，深度加 1
    
    return depth

代码解析

递归法

1. 递归终止条件：

   • 如果当前节点为空，返回深度 0。

2. 递归计算左右子树的深度：

   • 分别递归计算左子树和右子树的深度。

3. 返回最大深度：

   • 返回左右子树的最大深度加 1（当前节点的深度）。

迭代法（BFS）

1. 初始化：

   • 使用队列存储节点，初始时将根节点加入队列。
   • 初始化深度 depth 为 0。

2. 层次遍历：

   • 遍历当前层的所有节点，将它们的子节点加入队列。
   • 每遍历完一层，深度加 1。

3. 返回深度：

   • 遍历结束后，返回深度 depth。

复杂度分析

• 时间复杂度：O(n)，其中 n 是二叉树的节点数。每个节点被访问一次。
• 空间复杂度：
  • 递归法：O(h)，其中 h 是二叉树的高度，递归调用栈的深度为树的高度。
  • 迭代法：O(n)，队列的最大空间为树的宽度。

示例运行

示例 1

# 创建二叉树 [3,9,20,null,null,15,7]
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)

# 计算最大深度
print(maxDepth(root))  # 输出: 3

示例 2

# 创建二叉树 [1,null,2]
root = TreeNode(1)
root.right = TreeNode(2)

# 计算最大深度
print(maxDepth(root))  # 输出: 2

示例 3

# 创建空二叉树 []
root = None

# 计算最大深度
print(maxDepth(root))  # 输出: 0

总结

通过递归或迭代的方式，我们可以高效地计算二叉树的最大深度。递归法代码简洁，但可能受递归深度限制；迭代法使用队列进行层次遍历，适合处理较大的树。希望这篇题解对你有帮助！如果还有其他问题，欢迎继续提问！

关注我，获取更多算法题解和编程技巧！