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.

Solution

// singlePath: 从root往下走到任意点的最大路径，这条路径可以不包含任何点, 意味着可以直接舍去从根到左或者右的节点，如果为负数直接舍去，这是同Maximum Path Sum II 的区别，后者必须要包含一个跟节点。

// maxPath: 从树中任意到任意点的最大路径，这条路径至少包含一个点



为什么需要这个Singlepath, 函数本身返回任意点到任意点，这意味着，左子树，右子树，经过跟节点的路径，需要单独计算。



 Binary Tree Maximum Path Sum II 区别

"""
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
        maxpath, _= self.maxPathHelper(root)
        return maxpath

    def maxPathHelper(self, root):
        if root is None:
            return -sys.maxsize, 0  #最大路径不一定要穿过跟节点，所以如果不穿过，那么即为0

        left = self.maxPathHelper(root.left)
        right = self.maxPathHelper(root.right)

        maxpath = max(left[0],right[0],left[1] + right[1] + root.val) # 不能跟0比较，如果跟零比较那么最大值必须大于0了
        singlepath = max(left[1] + root.val, right[1] + root.val, 0) #需要同0比较，这样可以确定最大值是否需要穿过跟节点。

        return maxpath, singlepath