LC 124二叉树中的最大路径和Binary Tree Maximum Path Sum　困难

求二叉树中任一非空路径节点值之和的最大值，路径可经父节点连接左右子树。

思路 递归返回 val+max(左, 右)（负贡献取 0），全局更新 val+左+右 的弯路和。时间 O(n)。

class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        self.ans = root.val

        def gain(node):
            if not node:
                return 0
            l = max(gain(node.left), 0)
            r = max(gain(node.right), 0)
            self.ans = max(self.ans, node.val + l + r)
            return node.val + max(l, r)

        gain(root)
        return self.ans