# 124. Binary Tree Maximum Path Sum



![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-Mbjqulqffs5QaUcYUxi%2F-MbjxpVNDJ_meTrXbgti%2Fimage.png?alt=media\&token=840225ba-6261-428c-8c07-040ad7cf3eb2)

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-Mbjqulqffs5QaUcYUxi%2F-MbjxuKsHwnK2erLWBq2%2Fimage.png?alt=media\&token=1ff449ad-2374-42ed-8081-965f90069507)



![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-Mbjqulqffs5QaUcYUxi%2F-Mbjxb9F7SlvptexWJWp%2Fimage.png?alt=media\&token=38af20fd-1ce9-44a1-bbca-3c59eb2f652b)

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-Mbjqulqffs5QaUcYUxi%2F-MbjxhFah_l30g-XP06_%2Fimage.png?alt=media\&token=324f6ffc-dbc4-4bc7-a043-483ec1401405)

time: O(n)

space: O(H), where H is a tree height, to keep the recursion stack.

**計算子樹在一一合併, 左右根 post order**

**這題主要是要想到可以捨棄負的節點, 丟掉負的絕對比較能得到最大的結果**

**還有 res 是獨立計算的**

```java
class Solution {
    int res = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        helper(root);
        return res;
    }
    private int helper(TreeNode root) {
        if (root == null) return 0;
        int left = Math.max(0, helper(root.left)); // key point, abandon negtive 
        int right = Math.max(0, helper(root.right));
        
        // update max_sum if it's better to start a new path, 
        // res: origin path result, 
        // left + right + root.val => new path result
        res = Math.max(res, left + right + root.val); 
        return Math.max(left, right) + root.val;  // compare left, right
    }
}
```



why  do this?

```
int left = Math.max(0, helper(root.left)); // key point, abandon negtive 
int right = Math.max(0, helper(root.right));
        
```

ex: input: \[2,-1], ans = 2

if we don't max with 0

at last, res = 2-1 = 1

return Math.max(-1, 0) + 2 = 1

ans  = 1, it's wrong, so when cal left, right result, we should compare with 0, then it's the max value





### without global variable

use int\[] , it can be a memory

````java
```java
class Solution {
    public int maxPathSum(TreeNode root) {
        int[] result = new int[]{Integer.MIN_VALUE};
        dfs(root, result);
        return result[0];
    }
    private int dfs(TreeNode node, int[] result) {
        if (node == null) {
            return 0;
        }
        int left = Math.max(0, dfs(node.left, result));
        int right = Math.max(0, dfs(node.right, result));
        result[0] = Math.max(result[0], left + right + node.val);
        return Math.max(left, right) + node.val;
    }
}
```
````

### why return Math.max(left, right) + node.val;? -> for func\_max路徑

結論,&#x20;

求兩個東西&#x20;

1.也就是我們求一個 max down path sum （func\_max路徑）

2. 那有這個路徑, 之後就是拿來算 max path sum (拐點value + func\_max路徑(left node) + func\_max路徑(right node))

會是我們的答案, 因為 math path = 拐點 + 左右path max sum （只有一個拐點喔！
