[LeetCode] #124. Binary Tree Maximum Path Sum
題目
A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.
The path sum of a path is the sum of the node's values in the path.
Given the root of a binary tree, return the maximum path sum of any path.
直覺解
構想：
像 53. Maximum Subarray 那樣，把累加的數字都存進去 current，確定數字真的有比較大才會放進 max_sum 當作答案。但是，Maximum Subarray 的題目，因為給的是陣列，只要從 array[0] 迭代到 array[-1] 一個單一方向就行，但是這一題的 tree 有兩個分支，而且頂多只有一個節點的左右節點都會在 path 裡，其他節點只會有左節點或右節點，情況跟 Maximum Subarray 很不一樣，腦袋已經轉不過來了。
python 3 實作（失敗）：
class Solution:
def maxPathSum(self, roo
t: TreeNode) -> int:
max_sum = 0
current = -1000
return self.recursion(root, max_sum, current)
def recursion(self, root, max_sum, current):
if root is None:
return max_sum
if current + root.val < 0:
current = max(current, root.val)
else:
current += root.val
max_sum = max(current, max_sum)
max_sum = max(
self.recursion(root.left, max_sum, current),
self.recursion(root.right, max_sum, current)
)
return max_sum
⋯⋯其實我也不清楚自己寫了什麼東西⋯⋯
參考別人的解
參考後的解題構想
self.max_sum 負責儲存目前為止總和最大的路徑。比較的方向，是從葉子往根比較。
在當前的節點（recursion 中的 root）時，先計算「以左節點為根節點的 sub tree 中總和最大的路徑（這條路不能同時選擇左右節點）」和「以右節點為根節點的 sub tree 中總和最大的路徑（這條路不能同時選擇左右節點）」，然後判斷要不要把左節點或右節點加入「以當前節點為根節點的 sub tree 中的 Maximum Path Sum」（如果小於零的話就不要加入）
比較 self.max_sum 和「以當前節點為根節點的 sub tree 中的 Maximum Path Sum」哪個比較大，取大的那個
最後 return 「以當前節點為根節點的 sub tree 中總和最大的路徑（這條路不能同時選擇左右節點）」
自己的 python 3 實作：
class Solution:
def __init__(self):
self.max_sum = 0
def maxPathSum(self, root: TreeNode) -> int:
self.max_sum = root.val if root else 0
self.recursion(root)
return self.max_sum
def recursion(self, root):
if root is None:
return 0
left = max(0, self.recursion(root.left))
right = max(0, self.recursion(root.right))
self.max_sum = max(self.max_sum, root.val + left + right)
return max(left, right) + root.val
效能：
Runtime: 92 ms, faster than 48.81% of Python3 online submissions for Binary Tree Maximum Path Sum.
Memory Usage: 20.9 MB, less than 94.14% of Python3 online submissions for Binary Tree Maximum Path Sum.
Comments
Post a Comment