Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给出一颗二叉树,节点值-1000 <= Node.val <= 1000,节点数[1, 3 * 104],求其中一条节点值之和最大的一条path,返回最大的节点值之和
DFS,每次搜到某个节点,返回经过这个节点且通往其中一棵子树这一路的最大节点和,且更新全局最大值为以这个节点为父节点,path同时伸向该节点左右子树的最大节点和,注意节点值可能是负数,所以每步要和0取max

2014年1月用C++版本AC的题解见->http://www.cppblog.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

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理