leetcode [124] 二叉树中的最大路径和

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

给定一个非空二叉树，返回其最大路径和。

本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。

示例 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 maxPathSum(self, root: TreeNode) -> int:
        if root is None:
            return 0
        global maxval
        maxval = -999
        self.maxPathSumCore(root)
        return maxval

    def maxPathSumCore(self, root: TreeNode) -> int:
        if root is None:
            return -999
        global maxval
        if root.left is None and root.right is None:
            maxval = max(maxval, root.val)
            return root.val
        left = self.maxPathSumCore(root.left)
        right = self.maxPathSumCore(root.right)
        maxval = max(maxval, root.val, left, right, left + root.val, right + root.val, left + right + root.val)
        return max(root.val, left + root.val, right + root.val)