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

2023-04-16 00:00:00 算法 递归 深度

二叉树的最大深度是指从根节点到最深叶子节点的节点数。Python递归实现二叉树的最大深度算法的实现过程如下：

  1. 如果树为空，返回0；
  2. 否则，获取左子树的深度和右子树的深度，将较大的加1作为该树的深度；
  3. 递归计算左子树和右子树的深度。

以下是Python递归实现二叉树的最大深度算法的代码演示：

# 定义二叉树节点类
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

# 递归计算二叉树深度
def maxDepth(root):
    if not root:
        return 0
    left_depth = maxDepth(root.left)
    right_depth = maxDepth(root.right)
    return max(left_depth, right_depth) + 1

# 创建二叉树示例
root = TreeNode('p')
root.left = TreeNode('i')
root.right = TreeNode('d')
root.left.left = TreeNode('a')
root.left.right = TreeNode('n')
root.right.left = TreeNode('a')
root.right.right = TreeNode('n')
root.left.left.left = TreeNode('c')
root.left.left.right = TreeNode('o')
root.left.right.left = TreeNode('d')
root.right.left.left = TreeNode('e')
root.right.right.left = TreeNode('c')
root.right.right.right = TreeNode('o')
root.right.right.right.right = TreeNode('m')

# 计算二叉树深度
depth = maxDepth(root)
print('二叉树的最大深度为', depth)

输出结果：

二叉树的最大深度为 5

在本例中，我们创建了一个以字母“p”为根节点，共15个节点的二叉树示例，计算出该二叉树的最大深度为5。

相关文章