资源汇总
思路
利用后序遍历,先把左子树右子树的路径和求出来,如果左右子树的和小于等于0,则当成0相加。
代码
import sys
class Solution:
def __init__(self):
self.maxSum = -sys.maxsize-1
def maxPathSum(self, root: TreeNode) -> int:
self.oneSideMax(root)
return self.maxSum
def oneSideMax(self, root):
if root is None:
return 0
leftSum = max(0, self.oneSideMax(root.left))
rightSum = max(0, self.oneSideMax(root.right))
self.maxSum = max(self.maxSum, leftSum+rightSum+root.val)
# 因为只能选择一路,要么是左到拫,要么是右到根
return max(leftSum, rightSum) + root.val
为什么向上返回的和是 return max(leftSum, rightSum) + root.val
因为对于在第二层的 节点2 中,向上返回的值为 max(leftSum, rightSum) + root.val 意味着当前节点要被考虑到,当前节点要被考虑到的话只有两条路径,3->2 或者 0->2,要选路径和最大的值返回,显然是 max() + root.val