Binary Tree Maximum Path Sum II

Given a binary tree, find the maximum path sum from root.

The path may end at any node in the tree and contain at least one node in it.

Example

Given the below binary tree:

  1
 / \
2   3

return 4. (1->3)

Solution

为什么需要与零比较，主要是如果左右子树的值是负数，那么直接舍去，不需要。

"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        this.val = val
        this.left, this.right = None, None
"""
class Solution:
    """
    @param root the root of binary tree.
    @return an integer
    """
    def maxPathSum2(self, root):
        # Write your code here
        if root is None:
            return 0

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

        return max(left, right, 0) + root.val #包含一个点就是括号外，不包含就是括号里面