124. Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

For example: Given the below binary tree,

       1
      / \
     2   3

Return 6.

Solution:

class Solution(object):
    def maxPathSum(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        path_sum = [float('-inf')]

        def root_sum(node):
            if not node:
                return 0
            left = max(0, root_sum(node.left))
            right = max(0, root_sum(node.right))
            path_sum[0] = max(path_sum[0], left + right + node.val)
            return max(left, right) + node.val

        root_sum(root)
        return path_sum[0]

Related:

• 298. Binary Tree Longest Consecutive Sequence