我第一眼看到这个题想到的是类似于前缀和的思路，不过仔细想想应该是不对的，而且也不知道具体该怎么写。看了一下官方题解，来把思路捋一遍。首先，为了算出最大的路径和，我们考虑将该路径分成三部分，分别是节点，左子树和右子树。要求最大的路径和我们需要找到左右子树里各自的最大贡献值。这个贡献值定义是以某个节点为根节点的子树中寻找以该节点为起点的一条路径，使得该路径上的节点值和最大。具体而言，空节点的最大贡献值等于0，非空节点的最大贡献值等于节点值与其子节点中的最大贡献值之和（对于叶节点而言，最大贡献值等于节点值）。因此，如果我们求出了某个节点的左右子节点的最大贡献值，只要将这俩贡献值加上该节点的值就可以求的一个局部的最大路径和，当然如果左右子节点中某个节点的最大贡献值为负数，我们就不会加上该以子节点为根节点的路径（或者说，加上0）。然后我们再维护一个全局变量来存储最大路径和，在递归过程中更新值，最后得到的就是二叉树中的最大路径和。这个算法的时间复杂度是O（N），空间复杂度是O（N）。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def maxPathSum(self, root: TreeNode) -> int:
self.ans = float("-inf")
def maxGain(node):
if not node:
return 0
leftMaxGain = max(maxGain(node.left), 0)
rightMaxGain = max(maxGain(node.right), 0)
new = node.val + leftMaxGain + rightMaxGain
self.ans = max(new, self.ans)
return node.val + max(leftMaxGain, rightMaxGain)
maxGain(root)
return self.ansPREVIOUSlc236.二叉树的最近公共祖先
NEXTmq042.二叉树的最近公共祖先