Binary Tree Maximum path sum

Question

Given a binary tree, find the maximum path sum.

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

思路

对于root来说，最大路径有两种情况

1. 不通过root, 在左右两边的子树里
2. 通过root, 如果左child, 和右child通过他们的最大path > 0,就可以连到root上

然后比较三个

1. 左边子树里的最大path
2. 右边子树里的最大path
3. 通过root的最大path

注意,child return给上面的可以连的值应该是通过自己的path sum,而不一定是最大的， return 俩个值，maxSum, single

recursive, helper function

Solution

#!/usr/bin/python
# -*- coding: utf-8 -*-

"""
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                                                                                                            
        maxSum, single = self.maxPathSumHelper(root)
        return maxSum

    def maxPathSumHelper(self, root):
        #None时，maxSum为最小不应算，通过它的maxPathSum是0
        if not root:
            return -sys.maxint, 0

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

        #比较三种不同情况
        maxSum = max(left[0], right[0], left[1] + root.val + right[1])
        #对于return的通过本node的path,这个node必须是终点
        single = max(left[1] + root.val, right[1] + root.val, 0)

        return maxSum, single