給出一顆二叉樹，節(jié)點值-1000 <= Node.val <= 1000，節(jié)點數[1, 3 * 10
4]，求其中一條節(jié)點值之和最大的一條path，返回最大的節(jié)點值之和
DFS，每次搜到某個節(jié)點，返回經過這個節(jié)點且通往其中一棵子樹這一路的最大節(jié)點和，且更新全局最大值為以這個節(jié)點為父節(jié)點，path同時伸向該節(jié)點左右子樹的最大節(jié)點和，注意節(jié)點值可能是負數，所以每步要和0取max
2014年1月用C++版本AC的題解見->http://www.shnenglu.com/Uriel/articles/205482.html
1 #124
2 #Runtime: 125 ms
3 #Memory: 26 MB
4
5 # Definition for a binary tree node.
6 # class TreeNode(object):
7 # def __init__(self, val=0, left=None, right=None):
8 # self.val = val
9 # self.left = left
10 # self.right = right
11 class Solution(object):
12 def maxPathSum(self, root):
13 """
14 :type root: TreeNode
15 :rtype: int
16 """
17 self.ans = -40000000
18 def DFS(r):
19 if not r:
20 return 0
21 l_sum = DFS(r.left)
22 r_sum = DFS(r.right)
23 self.ans = max(self.ans, max(0, l_sum) + max(0, r_sum) + r.val)
24 return max(l_sum, r_sum, 0) + r.val
25 DFS(root)
26 return self.ans