二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。给你一个二叉树的根节点 root ，返回其 最大路径和 。

分析

• 变化的变量太多，需要固定一些，减少重复就可以进一步减少运算时间
• 可以定义一个最小单位，经过当前节点，并且是以当前节点为起点或者终点的路径
• 这样的的话，就可以分成四种情况，就是要嘛自己最大，要嘛加上左节点的最大路径最大，要嘛加上有节点的最大路径最大，要嘛左右节点的最大
• 但是返回只能返回前三种，有个全局变量记录四种的最大

# 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:

        self.max_sum = float("-inf")
        self.dfs(root)

        return self.max_sum


        
    # 这个dfs的作用就是返回经过当前节点的最大路径
    def dfs(self, root):

        if not root:
            return 0
        
        left_max = max(self.dfs(root.left), 0)
        right_max = max(self.dfs(root.right), 0)

        self.max_sum = max(self.max_sum, root.val + left_max + right_max)

        # 返回以改节点为起点或者终点的最大路径和
        return root.val + max(left_max, right_max)