原題
給出一棵二叉樹，尋找一條路徑使其路徑和最大，路徑可以在任一節(jié)點中開始和結(jié)束（路徑和為兩個節(jié)點之間所在路徑上的節(jié)點權(quán)值之和）
給出一棵二叉樹：
1
/ \
2 3
返回 6
解題思路
- 首先播歼，想一個簡化版(single path)，找從
root到任意點得最大值。類似于maxDepth佑菩，每次加root.val而不再是+1 - 求單路的時候，如果
root加左兒子單路或者右兒子單路最后的值都小于0裁赠，則返回0殿漠，意味著不要root開始的這個單路了 - 本題思路，divide & conquer
求最大路徑和就等于下面三個值的最大值： - 左子樹的最大路徑和
- 右子樹最大路徑和
- 左子樹單路 + 右子樹單路 + root.val
完整代碼
# 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
"""
res, _ = self.helper(root)
return res
def helper(self, root):
if not root:
return -sys.maxint, 0
left = self.helper(root.left)
right = self.helper(root.right)
singlePathSum = max(left[1] + root.val, right[1] + root.val, 0)
maxPathSum = max(left[0], right[0], left[1] + right[1] + root.val)
return maxPathSum, singlePathSum
