原题地址：https://oj.leetcode.com/problems/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.
For example:
Given the below binary tree,
1
/ \
2 3
Return 6.
解题思路：这道题是在树中寻找一条路径，这条路径上的节点的和为最大，起点和终点只要是树里面的节点就可以了。这里需要注意的一点是：节点值有可能为负值。解决这道二叉树的题目还是来使用递归。例如下面这棵树：
1
/ \
2 3
/ \ / \
4 5 6 7
对于这棵树而言，和为最大的路径为：5->2->1->3->7。
那么这条路径是怎么求出来的呢？这里需要用到一个全局变量Solution.max，可以随时被更大的路径和替换掉。在函数递归到左子树时：最大的路径为：4->2->5。但此时函数的返回值应当为4->2和5->2这两条路径中和最大的一条。右子树同理。而Solution.max用来监控每个子树中的最大路径和。那么思路就是：（左子树中的最大路径和，右子树中的最大路径和，以及左子树中以root.left为起点的最大路径（需要大于零）+右子树中以root.right为起点的最大路径（需要大于零）+root.val），这三者中的最大值就是最大的路径和。
代码：
# Definition for a binary tree node
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None class Solution:
# @param root, a tree node
# @return an integer
def maxsum(self, root):
if root == None: return 0
sum = root.val
lmax = 0; rmax = 0
if root.left:
lmax = self.maxsum(root.left)
if lmax > 0:
sum += lmax
if root.right:
rmax = self.maxsum(root.right)
if rmax > 0:
sum += rmax
if sum > Solution.max: Solution.max = sum
return max(root.val, max(root.val + lmax, root.val + rmax)) def maxPathSum(self, root):
Solution.max = -10000000
if root == None: return 0
self.maxsum(root)
return Solution.max