Python递归实现二叉树的最小深度算法

2023-04-16 00:00:00 算法 递归 最小

二叉树的最小深度是从根节点到最近叶子节点的最短路径长度。实现该算法的一个常用方法是递归。递归地计算每个子树的最小深度并返回较小的那个。

具体的实现步骤如下：

  1. 首先判断根节点是否为空，如果为空，则返回0。

  2. 如果根节点没有左子树和右子树，则该节点为叶子节点，返回1。

  3. 如果根节点只有左子树或者只有右子树，则需要继续递归计算该子树的最小深度。

  4. 如果根节点既有左子树又有右子树，则需要分别递归计算左子树和右子树的最小深度，两者取较小值加1即为根节点的最小深度。

下面是Python代码的实现：

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

def minDepth(root: TreeNode) -> int:
    if not root:
        return 0
    if not root.left and not root.right:
        return 1
    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

例如，对于以下的二叉树：

          1
         / \
        2   3
       / \
      4   5

调用 minDepth 函数，应该返回2，因为最近的叶子节点为4或5，其深度为2。

相关文章