# 124. Binary Tree Maximum Path Sum

![](/files/-MbjxpVNDJ_meTrXbgti)

![](/files/-MbjxuKsHwnK2erLWBq2)

![](/files/-Mbjxb9F7SlvptexWJWp)

![](/files/-MbjxhFah_l30g-XP06_)

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路徑

結論, 

求兩個東西 

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 （只有一個拐點喔！


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/tree/124.-binary-tree-maximum-path-sum.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.