思路与求直径一样

枚举最高点（以其为根节点）

在当前节点有三种选择：（目前路径和为s）
1、往左走，s+L 
2、往右走，s+R 
3、不走，s，当L,R都是负数

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        self.ans = -float('inf')
        self.dfs(root)
        return self.ans

    # 返回从root向下走的最大值(包括root的值)
    def dfs(self, root):
        if not root: return 0

        left = self.dfs(root.left)
        right = self.dfs(root.right)

        self.ans = max(self.ans, left + root.val + right) 
        return max(0, root.val + max(0, max(left, right))) 
        # root.val + max(0, max(left, right)反映了当前节点三种选择，不走或只走左右其中一条
        # max(0,。。）反映当前节点的父节点的两种选择，如果不管儿子往下走不走都是负数，该子节点也不会要


# 思路与求直径一样
# 枚举最高点（以其为根节点）
# 在当前节点有三种选择：（目前路径和为s）
# 1、往左走，s+L 
# 2、往右走，s+R 
# 3、不走，s，当L,R都是负数