# **Leetcode筆記(Binary Tree Maximum Path Sum)** :::info :information_source: 題目 : Binary Tree Maximum Path Sum, 類型 : binary tree , 等級 : hard 日期 : 2023/03/29，2023/05/24，2023/07/07，2023/10/30 ::: ### 嘗試 2023/05/24 ```python class Solution: def maxPathSum(self, root: Optional[TreeNode]) -> int: res = [float("-inf")] def dfs(node): if not node: return 0 left = max(dfs(node.left), 0) right = max(dfs(node.right), 0) # root + right + lrft (小樹自己繞一圈) res[0] = max(res[0], node.val + left + right) # 但還是繼續算 return node.val + max(left, right) return max(dfs(root), res[0]) ``` 2023/07/07 每次都回傳root + max(left, right)，也就是只選中 + 左或中 + 右，在計算過程中也可以順便更新中 + 左 + 右， 特別留意的是，如果左右為負的話，可以直接只選中(因為不管選哪個，都會使sum變得更小) ```python class Solution: def __init__(self): self.res = float("-inf") def maxPathSum(self, root: Optional[TreeNode]) -> int: self.dfs(root) return self.res def dfs(self, node): if not node: return 0 # 如果left right leaf為負 可以直接忽略 只選root回傳 left = max(self.dfs(node.left), 0) right = max(self.dfs(node.right), 0) self.res = max(self.res, node.val + left + right) return node.val + max(left, right) ``` 2023/10/30 ```python class Solution: def __init__(self): self.res = float("-inf") def maxPathSum(self, root: Optional[TreeNode]) -> int: def findMax(node): if not node: return 0 leftSum = max(0, findMax(node.left)) rightSum = max(0, findMax(node.right)) self.res = max(self.res, node.val + leftSum + rightSum) return max(node.val + leftSum, node.val + rightSum) findMax(root) return self.res ``` --- ### **優化** 時間複雜度為 $O(n)$，其中 $n$ 是二叉樹的節點數量。這是因為在每個節點上都會執行一次 DFS 遍歷 這個程式碼的空間複雜度為 $O(h)$，其中 $h$ 是二叉樹的高度。這是因為在遞迴過程中，會使用 $O(h)$ 的額外空間，其中 $h$ 是函數調用堆棧的最大深度。 ```python class Solution: def maxPathSum(self, root: Optional[TreeNode]) -> int: res = [root.val] def dfs(node): if not node: return 0 # 回傳的是單支的最大值 leftmax = dfs(node.left) rightmax = dfs(node.right) # 如果是負數 則寧可取0 # 基本上這種變成0的取法 已經綜合考慮到單純加左樹或右樹 leftmax = max(leftmax, 0) rightmax = max(rightmax, 0) # 四個可能 : root右 / root左 / root / root右左 # root / root右左 res[0] = max(res[0], node.val + leftmax + rightmax) # root右 / root左 return node.val + max(leftmax, rightmax) dfs(root) return res[0] ``` --- **:warning: 錯誤語法** :::warning 似乎如果用list[0]去操作的話，就不會遇到local variable 'res' referenced before assignment 這個錯誤表示在函數中使用了一個未被賦值的局部變數。在 Python 中，函數內部的變量作用域是局部的，因此必須在函數內部使用 = 賦值運算符將變量初始化。 ::: **:thumbsup:學習** :::success The path sum of a path is the sum of the node's values in the path. ::: **思路** **講解連結** https://www.youtube.com/watch?v=Hr5cWUld4vU Provided by. NeetCode ###### tags: `binary tree` `hard` `leetcode`