LeetCode124.二叉树中的最大路径与|sum题目给定一个非空二叉树，返回它的最大路径和。在这个问题中，路径被定义为从树中的任何节点开始并到达任何节点的序列。该路径至少包含一个节点，不一定经过根节点。示例1：输入：[1,2,3]1/\23输出：6示例2：输入：[-10,9,20,null,null,15,7]-10/\920/\157输出：42解题思路：递归题目中给出的路径概念是指【从树中任意一个节点开始，到达任意一个节点的序列。该路径至少包含一个节点，不一定经过根节点]。也就是说，需要路径和来计算节点所能提供的最大贡献值。节点所能提供的贡献值分为以下几部分：空节点提供的贡献值为0；非空节点提供的贡献值等于当前节点的值与其子节点提供的最大贡献值之和。现在用例1来分析解释一下：输入：[1,2,3]1/\23这里叶子节点2,3可以提供2,3的贡献值，叶子节点1可以提供一个贡献1+2或1+3的值。那么我们假设：如果节点1前面有一个父节点，那么这里的可能路径就会变成：2+1+32+1+1的父节点3+1+1的父节点第一种情况是求最大路径节点的总和。这里一个节点的最大路径和取决于该节点及其左右子节点的最大贡献值之和。当然这里如果子节点的贡献值是负数，那就选择不包含。因为负的贡献值相加会使结果变小。对于第二种和第三种情况，这里就是递归求出左右子节点的贡献值，从中选出更好的解。这里最重要的是维护一个存储最大路径和的变量max_path_sum，在递归过程中维护和更新这个值以获得最大值。具体代码实现如下。代码实现#定义一个二叉树节点。#classTreeNode:#def__init__(self,x):#self.val=x#self.left=None#self.right=NoneclassSolution:def__init__(self):#存储最大路径和self.max_path_sum=float('-inf')defmaxPathSum(self,root:TreeNode)->int:defmax_contr(node):#递归求节点的最大贡献值#同时保持通过节点的最大路径和#的贡献空节点的值为0ifnotnode:return0#递归计算左子节点的贡献值left=max(0,max_contr(node.left))#递归计算右子节点的贡献值right=max(0,max_contr(node.right))#通过当前节点的最大路径和self.max_path_sum=max(self.max_path_sum,left+node.val+right)#当前节点的贡献值，取更好的左右子节点方案node_contr=node.val+max(0,max(left,right))#这里返回的贡献值是给upstr的eamnodeofthecurrentnodereturnnode_contrmax_contr(root)returnself.max_path_sumimplementationresultssummary从题目中得到的信息可以知道需要最大路径和，需要得到节点能量节点所能提供的贡献值分为两部分：空节点的贡献值为0；对于非空节点，当前节点所能提供的贡献值就是当前节点及其子节点的值。可以提供的最大贡献值的总和对于非空节点，我们需要递归的方法来获取每个节点的贡献值。同时，需要保持最大路径和。这里，节点的路径和取决于当前节点的值及其左右子节点的最大贡献值。这里注意：当贡献值为负时，不计入该节点的最大路径和。文章原创，如果觉得写的不错，请点个关注点个赞。微信公众号《书所集录》同步更新，也欢迎大家关注点赞。
