LeetCode 124.二叉树中的最大路径和

给定一个非空二叉树，返回其最大路径和。
本题中，路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。
该路径至少包含一个节点，且不一定经过根节点。

示例 1：
输入：[1,2,3]

   1
  / 
 2   3

输出：6

示例 2：
输入：[-10,9,20,null,null,15,7]

-10
/
9 20
/
15 7

输出：42

class Solution:
    def __init__(self):
        self.maxSum = -float('inf')
    def maxPathSum(self, root: TreeNode) -> int:
        def maxGain(root):
            if root is None:
                return 0
            leftGain = max(0, maxGain(root.left))
            rightGain = max(0, maxGain(root.right))
            self.maxSum = max(self.maxSum, root.val + leftGain + rightGain)
            return root.val + max(leftGain, rightGain)

        maxGain(root)
        return self.maxSum

        """
        时间复杂度：O(n)
        空间复杂度：O(n)
        递归的入口和出口、返回值，全局状态的更新逻辑
        """