Binary Tree Maximum Path Sum

Source

• lintcode: Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

Example
Given the below binary tree:

  1
 / \
2   3
return 6.

Python

import sys

"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""
class Solution:
    """
    @param root: The root of binary tree.
    @return: An integer
    """
    def maxPathSum(self, root):
        # write your code here
        result=[-sys.maxint-1]
        self.helper(root, result)
        return result[0]

    def helper(self, root, result):
        if root is None:
            return 0
        l = self.helper(root.left, result)
        r = self.helper(root.right, result)
        m=root.val
        if l>0:
            m+=l
        if r>0:
            m+=r

        result[0] = max(result[0], m)
        if max(l, r)>0:
            return max(l, r)+root.val
        return root.val