编写一个函数,接收一棵树作为参数,返回树中任意路径上节点值的最大和。
创始人
2024-12-06 18:00:22
0

我们可以使用递归的方法来解决这个问题。我们先定义一个函数 max_sum(node),这个函数以树的节点作为参数,返回以该节点为起点的最大路径和。然后,我们就可以在整个树中找到最大的路径和。

在 max_sum(node) 中,我们需要对每个节点的两个子节点分别调用 max_sum,找到它们的最大路径和。然后我们可以计算出以该节点为顶点的路径最大和为 node.value + max(left_sum, right_sum)。最后在所有节点调用 max_sum,找到最大的路径和即可。

下面是代码示例:

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

def max_sum(node: TreeNode) -> int:
    if node is None:
        return 0
    
    left_sum = max_sum(node.left)
    right_sum = max_sum(node.right)
    
    return node.value + max(0, max(left_sum, right_sum))

def max_path_sum(root: TreeNode) -> int:
    if root is None:
        return 0
    
    left_sum = max_path_sum(root.left)
    right_sum = max_path_sum(root.right)
    
    return max(max_sum(root), max(left_sum, right_sum))

给定下面的二叉树:

     1
    / \
   2   3
  / \     
 4   5    

调用 max_path_sum(root) 将返回 12,对应路径为 4->2->1->3。

相关内容

热门资讯

两分钟详情!永州跑胡子辅助器,... 两分钟详情!永州跑胡子辅助器,智星德州有挂(详细透视辅助挂教程);值得一提的是,永州跑胡子辅助器计算...
三分钟详情!顺欣茶楼辅助教程,... 三分钟详情!顺欣茶楼辅助教程,wepoke游戏真的是有挂的(详细透视辅助黑科技教程);wpk透视辅助...
4分钟总结!一起宁德钓蟹黑科技... 4分钟总结!一起宁德钓蟹黑科技,wpk代打是真的(详细透视辅助app教程);一起宁德钓蟹黑科技软件透...
5分钟了解!哥哥跑得快怎么赢,... 5分钟了解!哥哥跑得快怎么赢,约局互娱辅助(详细透视辅助神器教程)关于哥哥跑得快怎么赢机制的,其中提...
2分钟方法!开心游戏跑得快有挂... 2分钟方法!开心游戏跑得快有挂吗,传奇扑克辅助(详细透视辅助助手教程);一、开心游戏跑得快有挂吗有挂...
2分钟教学!福建天天开心辅助工... 2分钟教学!福建天天开心辅助工具,wepoke软件收费(详细透视辅助app教程)1、每一步都需要思考...
2分钟教程!腾讯广东麻将助赢神... 2分钟教程!腾讯广东麻将助赢神器,nzt德州辅助软件(详细透视辅助黑科技教程);腾讯广东麻将助赢神器...
七分钟辅助挂!哈局十三张怎么赢... 七分钟辅助挂!哈局十三张怎么赢,德扑之星可以看底牌(详细透视辅助插件教程)相信很多朋友都在电脑上玩过...
5分钟技巧!传送屋激k有挂吗,... 传送屋激k有挂吗新手教程相关信息汇总(需添加指定薇757446909获取下载链接);5分钟技巧!传送...
三分钟教程!钱塘十三水有挂是真... 三分钟教程!钱塘十三水有挂是真的吗,wpk线上实战(详细透视辅助app教程)1、很好的工具软件,可以...