Python求解二叉树最小深度的两种实现方案

程一诺

发布时间：2026-10-13| 4人浏览过

原创

本文详解Python中计算二叉树最小深度的两种方法。最小深度定义为根节点到最近叶子节点的最短路径节点数，其中叶子节点指无子树的节点。文章对比了基于层序遍历的迭代法与处理单子树情况的递归法，提供了完整代码示例及LeetCode原题链接，帮助开发者掌握核心逻辑与边界条件处理。

二叉树最小深度定义与示例

确定给定二叉树的最小深度

最小深度是指从根节点到最近叶子节点路径上所经过的节点总数

需注意：叶子节点是指没有任何子节点的节点

示例：

给定二叉树结构为 [3,9,20,null,null,15,7]

3 / \ 9 20 / \ 15 7 其最小深度返回值为 2。

方法一：采用算法逐层遍历二叉树，当发现某层中存在无子树的节点时，立即返回当前层深度，该值即为二叉树的最小深度

迭代法实现：层序遍历


def minDepth(self, root):
    """
    :type root: TreeNode
    :rtype: int
    """
    if not root:
      return 0
    curLevelNodeList = [root]
    minLen = 1
    while curLevelNodeList is not []:
      tempNodeList = []
      for node in curLevelNodeList:
        if not node.left and not node.right:
          return minLen
        if node.left is not None:
          tempNodeList.append(node.left)
        if node.right is not None:
          tempNodeList.append(node.right)
      curLevelNodeList = tempNodeList
      minLen += 1
    return minLen

方法二：利用递归解决此题，与"二叉树的最大深度"存在差异。核心区别在于处理"节点仅存在一棵子树"的情形，此时最小深度路径必然包含该子树上的节点

递归法实现：处理单子树情况


def minDepth(self, root):
    """
    :type root: TreeNode
    :rtype: int
    """
    if not root:
      return 0
    if not root.left and root.right is not None:
      return self.minDepth(root.right)+1
    if root.left is not None and not root.right:
      return self.minDepth(root.left)+1
    left = self.minDepth(root.left)+1
    right = self.minDepth(root.right)+1
    return min(left,right)

题目来源：https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/description/

以上为本文全部内容，希望有助于大家的学习，欢迎继续支持本站。