Binary Tree Max 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 does not need to go through the root.

For example: Given the below binary tree,

       1
      / \
     2   3
Return 6.

解题方法

对于数的问题，很多都可以用recursive的思想来解，其实也就是divide and conquer, 将大问题不断地分解成小问题。 我们可以通过发现root的结果与左右child的结果有什么关系 来入手。

对于每一个root, 这个max path sum有三种可能：

• 不通过root, 在左子树里
• 不通过root, 在右子树里
• 通过root,与左右两边的child连接

对于每个root都要比较这三种情况，从而得到最大的path sum, 所以在child往上返回 的时候，不仅仅要返回最大的值，也要返回以这个child自身为一个end的最大path sum. 有一点像DP里面global, local的关系。

所以每个recursive call会返回两个值，再进行比较判断。在判断比较的时候也要注意， 选取global最大结果的时候要取max,而在取通过自己的single path sum的时候，还要与0比较， 因为如果结果是负的，在上面连接这一个child的时候就应该将它舍去，就是0.

recursive返回的条件：

当节点为None的时候，因为节点value也有可能是负数，所以maxpathsum应该是最小整数 ，对于Python就是-sys.maxint,而通过它自申的最大path sum是0

Solution

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def maxPathSum(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        maxPathSum, single = self.PathSumHelper(root)
        return maxPathSum

    def PathSumHelper(self, root):
        if not root:
            return -sys.maxint, 0

        leftMax, leftSingle = self.PathSumHelper(root.left)
        rightMax, rightSingle = self.PathSumHelper(root.right)
        globalMax = max(leftMax, rightMax, root.val + leftSingle + rightSingle)
        singleMax = max(leftSingle + root.val, rightSingle + root.val, 0)

        return globalMax, singleMax

Reference