题目来源：

　　https://leetcode.com/problems/binary-tree-maximum-path-sum/

---

 

题意分析：

　　给定一棵树，找出一个数值最大的路径，起点可以是任意节点或者叶子。

---

 

题目思路：

　　我们可以先找路径的最大mr,ml，那么最大值是max（solve(root),solve(left),solve(right), max(mr + root.val + ml, root.val))。

---

 

代码（python）：

　　

 

# Definition for a binary tree node.# class TreeNode(object):#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Noneclass Solution(object):    def maxPathSum(self, root):        """        :type root: TreeNode        :rtype: int        """        if root == None:            return 0        Solution.maxsum = root.val        def solve(root):            if root == None:                return 0            sum,l,r = root.val,0,0            if root.left:                l = solve(root.left)                if l > 0: sum += l            if root.right:                r = solve(root.right)                if r > 0: sum += r            Solution.maxsum = max(Solution.maxsum,sum)            #print(Solution.maxsum)            return max(root.val,max(root.val + l,root.val+r))        solve(root)        return Solution.maxsum