208 - 124 二叉树中的最大路径和

题目

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

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

示例 1:

输入: [1,2,3]

   1
  / \
 2   3

输出: 6

示例 2:

输入: [-10,9,20,null,null,15,7]

-10 / 9 20 / 15 7

输出: 42

解答

递归

计算左子树、右子树，加上当前节点的值

https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/solution/er-cha-shu-de-zui-da-lu-jing-he-by-leetcode/

class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        max_sum = float('-inf')

        def max_gain(node):
            nonlocal max_sum
            if not node:
                return 0
            left = max(max_gain(node.left), 0)
            right = max(max_gain(node.right), 0)
            price_newpath = node.val + left + right
            max_sum = max(max_sum, price_newpath)
            return node.val + max(left, right)
        max_gain(root)
        return max_sum

Runtime: 88 ms, faster than 75.56% of Python3 online submissions for Binary Tree Maximum Path Sum.

Memory Usage: 20.2 MB, less than 100.00% of Python3 online submissions for Binary Tree Maximum Path Sum.

class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        res = float('-inf')

        def helper(root):
            nonlocal res
            if not root:
                return 0
            left = helper(root.left)
            right = helper(root.right)
            res = max(left+right+root.val, res)
            return max(0, max(left, right) + root.val)
        helper(root)
        return res

Runtime: 72 ms, faster than 99.59% of Python3 online submissions for Binary Tree Maximum Path Sum.

Memory Usage: 20.2 MB, less than 100.00% of Python3 online submissions for Binary Tree Maximum Path Sum.

光头大佬版本。。

https://leetcode.com/problems/binary-tree-maximum-path-sum/discuss/39919/8-10-lines-two-solutions

class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        def maxsums(node):
            if not node:
                return [-2**31]*2
            left = maxsums(node.left)
            right = maxsums(node.right)
            return [node.val+max(left[0], right[0], 0),
                    max(left+right+[node.val+left[0]+right[0]])]
        return max(maxsums(root))

Runtime: 92 ms, faster than 56.23% of Python3 online submissions for Binary Tree Maximum Path Sum.

Memory Usage: 20.3 MB, less than 100.00% of Python3 online submissions for Binary Tree Maximum Path Sum.