leetcode124. 二叉树中的最大路径和

给定一个非空二叉树，返回其最大路径和。

本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。

示例 1:

输入: [1,2,3]1/ \2   3输出: 6

示例 2:

输入: [-10,9,20,null,null,15,7]-10/ \9  20/  \15   7输出: 42（15+7+20）

---

方法：递归

思路：

我们首先考虑什么样的路径可以是最大路径，根据题意，只要是一个结点到另一结点即可。那么我们可以分成两种：

• 单向路径，即路径中所有的结点都不在同一层，比如示例2中的-10→20→7。
• 双向路径，路径中，以根节点为最高层，左右两个单路径向两边延伸，比如示例二中的答案15←20→7。

我们考虑以每一个结点为根，可以构成的最大单向路径和maxgain为多少，叶节点的maxgain就为它本身的值，其他结点的maxgain则为它自己的值与它左右结点中较大的maxgain之和。

如示例2中，首先15和7的maxgain为本身，然后20的maxgain为20+max(15,7)=35，然后9的maxgain为本身，-10的maxgain为-10+max(9,35)=25。

由上面的过程可以看出，这是一个从下到上的计算过程，因此用DFS递归可以完成计算。

我们再考虑答案与maxgain的关系，如果以某个点node为路径的根，那么双向路径的和为

node.val+maxgain(node.left)+maxgain(node,right)；

单向路径为

node.val+maxgain(node.left)或node.val+maxgain(node.right)。

我们要找到这个结点为根的最大路径和，那么就是上面三个式子的最大值，而只有在左结点或右结点的maxgain<0，答案才会是下面的式子，所以我们首先判断左右结点的maxgain是不是小于0，如果小于0，置为0，这样就都可以使用上面的式子来表示了。

由于计算路径和的时候，所需的值都是这个节点以及下一层的值，所以在遍历计算maxgain的同一个递归即可完成，只要使用一个全局变量更新结果即可。

代码：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = Noneclass Solution:def __init__(self):self.res = float('-inf')def maxPathSum(self, root: TreeNode) -> int:#该函数返回root为根的最大单项路径长度和，同时更新答案self.resdef maxgain(root):if not root:return 0#获取root的左右结点的最大单路径和，如果小于0则忽略           left = max(maxgain(root.left),0)right = max(maxgain(root.right),0)#以root为根，加上左右两个最大路径即为以root为根的最大双向路径和（有一个为0时为单向路径）summ = root.val + left + right#更新最大值self.res = max(self.res,summ)return root.val + max(left,right)maxgain(root)#返回答案return self.res

结果：