外部路径长度是指从根节点到所有叶节点的路径长度之和。针对正则二叉树,我们可以使用以下递归函数来计算它的外部路径长度:
def external_path_length(node, depth=0):
if node is None:
return 0
if node.left is None and node.right is None: # 如果当前节点是叶节点,则返回节点的深度
return depth
return depth + external_path_length(node.left, depth + 1) + external_path_length(node.right, depth + 1)
在这个函数中,我们用'depth”参数来跟踪每个节点所在的深度。如果节点是叶节点,则返回该节点的深度;否则,递归计算该节点的左右子树的外部路径长度,并将它们相加。
我们可以使用以下代码来测试此函数:
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# 构造一棵正则二叉树
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)
# 计算该树的外部路径长度
external_path_len = external_path_length(root)
print(external_path_len) # 输出结果为 10
该代码首先创建了一棵正则二叉树,并将其赋给名为'root”的变量。然后,我们调用上面定义的'external_path_length”函数来计算该树的外部路径长度。最终,我们打印该结果(输出应为10)。