分析
最大路径和可以转化成左右子树的和
用maxSum记录当前的最大路径和（左/右子树选一个最大的）
对左右孩子分别取maxSum如果小于0的话就舍弃了，直接算0重新来算过
然后统计一次当前路径的和（左+右+当前）
然后ans求max
最后return的是root.val 加上 左/右路径的最大值
然后调用该函数即可
ac code
# 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: Optional[TreeNode]) -> int:
ans = -inf
def maxSum(root):
nonlocal ans
if not root:
return 0
# 左右孩子的累计和取正的，否则取0
leftSum = max(0, maxSum(root.left))
rightSum = max(0, maxSum(root.right))
# 统计一次当前路径
now = root.val + leftSum + rightSum
ans = max(ans, now)
# 返回的是包括当前节点的左/右路径
return root.val + max(leftSum, rightSum)
maxSum(root)
return ans
总结
路径最大总和 -》 左右子树的最大和
左右子树如果小于0就丢弃了，算作0重新算（有点算子数组的最大和，如果小于0就丢掉这种思路）
然后ans就是（左 + 右 + 当前）取max
然后返回的是当前 + max（左，右）
这个感觉就是树状dp了
当累计和小于0就弃用重新选为0再次统计即可
