---
# System prepended metadata

title: '**Leetcode筆記(Binary Tree Maximum Path Sum)**'
tags: [hard, binary tree, leetcode]

---

# **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`