29 | 面试题：二叉树的最大和最小深度-算法面试通关 50 讲

当前位置:　首页>> 技术小册>> 算法面试通关 50 讲

29 | 面试题：二叉树的最大和最小深度

在算法面试中，二叉树相关的问题是常见的考点之一，它们不仅考察了求职者对数据结构基础知识的掌握程度，还检验了其在递归、迭代等算法设计方面的能力。其中，“二叉树的最大和最小深度”问题是一个既经典又富有挑战性的问题，它要求我们在给定的二叉树中找出从根节点到最远叶子节点的最长路径（即最大深度）和最短路径（即最小深度，通常不考虑空树的情况）。下面，我们将详细探讨这一问题的解法，包括递归和迭代两种主要思路。

一、问题定义

首先，明确问题的定义：

二叉树的深度：从根节点到最远叶子节点的最长路径上的节点数。
最大深度：在二叉树中，所有路径中的最大深度。
最小深度（非空树）：在二叉树中，所有路径中的最小深度。注意，如果树为空，则深度讨论无意义；但在实际面试场景中，通常会假设树非空或明确说明如何处理空树的情况。

二、递归解法

递归是解决二叉树深度问题的直观方法，因为它自然地反映了树的结构——将大问题分解为小问题。

2.1 最大深度

对于求最大深度，我们可以定义一个递归函数maxDepth(TreeNode root)，该函数检查当前节点是否为空：

如果为空，返回0（因为空树没有深度）。
否则，递归地计算左子树和右子树的最大深度，然后取两者中的较大值加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):
    if not root:
        return 0
    return max(maxDepth(root.left), maxDepth(root.right)) + 1

2.2 最小深度

求最小深度时，需要注意到最小深度可能由单侧的子树决定（尤其是当另一侧为空时）。因此，递归函数minDepth(TreeNode root)需要稍作调整：

如果为空，返回0（但在实际应用中，通常认为空树的最小深度无意义，这里仅为递归结束条件）。
如果只有一侧子树非空，返回该侧子树的最小深度加1。
如果两侧子树均非空，则返回两者中较小值加1。

def minDepth(root):
    if not root:
        return 0  # 注意：实际使用中可能需要抛出异常或返回特定值表示空树
    if not root.left:
        return minDepth(root.right) + 1
    if not root.right:
        return minDepth(root.left) + 1
    return min(minDepth(root.left), minDepth(root.right)) + 1

三、迭代解法

虽然递归解法直观且易于实现，但在处理深层递归时可能会遇到栈溢出的问题。迭代解法，尤其是利用栈（或队列，对于广度优先搜索BFS求最小深度）来模拟递归过程，可以有效避免这一问题。

3.1 最大深度（迭代，深度优先搜索DFS）

使用栈进行深度优先搜索（DFS）可以迭代地计算最大深度。算法流程如下：

初始化一个栈和一个变量来记录当前深度。
将根节点和初始深度（1）压入栈中。
当栈不为空时，循环执行以下步骤：
- 弹出栈顶元素（节点和当前深度）。
- 如果节点非空，更新最大深度（如果当前深度大于已知的最大深度）。
- 先右后左（或先左后右，取决于遍历顺序）将子节点和当前深度加1压入栈中。

def maxDepthIterative(root):
    if not root:
        return 0
    stack, max_depth = [(root, 1)], 0
    while stack:
        node, depth = stack.pop()
        if node:
            max_depth = max(max_depth, depth)
            if node.right:
                stack.append((node.right, depth + 1))
            if node.left:  # 注意先右后左是为了保证先遍历到最深的节点
                stack.append((node.left, depth + 1))
    return max_depth

3.2 最小深度（迭代，广度优先搜索BFS）

求最小深度时，广度优先搜索（BFS）是更自然的选择，因为它能逐层遍历树，直到找到第一个叶子节点。算法流程如下：

初始化一个队列和一个变量来记录当前层数。
将根节点和层数0（实际上从1开始计数，但为了方便计算，可以用层数变化来表示）加入队列。
当队列不为空时，循环执行以下步骤：
- 弹出队列首元素（节点和当前层数）。
- 如果节点是叶子节点，返回当前层数加1。
- 否则，将非空子节点和当前层数加1加入队列。

from collections import deque
def minDepthIterative(root):
    if not root:
        return 0  # 实际上，对于非空树的最小深度问题，这里应返回错误信息或特定值
    queue = deque([(root, 1)])  # (node, level)
    while queue:
        node, level = queue.popleft()
        if not node.left and not node.right:
            return level
        if node.left:
            queue.append((node.left, level + 1))
        if node.right:
            queue.append((node.right, level + 1))
    # 理论上不会执行到这里，除非输入为空树且未处理空树情况
    return -1  # 返回一个不可能的值表示错误或异常情况

四、总结

通过本章节的学习，我们深入探讨了二叉树的最大和最小深度的计算方法，包括递归和迭代两种解法。递归解法直观易懂，但在处理深层树时可能遇到栈溢出的问题；迭代解法，特别是使用栈的DFS和队列的BFS，提供了更稳健的解决方案。掌握这些解法不仅有助于应对面试中的相关问题，也是深入理解二叉树结构和算法设计的重要一步。