LeetCode 124. [Python] Binary Tree Maximum Path Sum
原题链接
困难
作者:
徐辰潇
,
2021-02-05 00:16:45
,
所有人可见
,
阅读 477
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def maxPathSum(self, root: TreeNode) -> int:
#TS: O(total nodes)
#SC: O(total nodes)
#The optimal path may not be leaf to leaf
#Two situtations:
#1. one nodes to another nodes, passing the common ancestors of the start and end nodes, just like example 2
#2. from one nodes to its parents, like
# -1
# -2 10
# 20
self.res = -sys.maxsize
self.dfs(root)
return self.res
def dfs(self, root):
if not root:
return 0
#leftMaxSum defines the maxsum of the leftsubtruee of the root, connected with the root
leftMaxSum = self.dfs(root.left)
#rightMaxSum defines the maxsum of the rightsubtruee of the root, connected with the root
rightMaxSum = self.dfs(root.right)
#update self.res, corresponding to situation 1
self.res = max(self.res, leftMaxSum + root.val + rightMaxSum)
#return, corresponding to situation 2
return max(0, root.val + max(leftMaxSum, rightMaxSum))