124. Binary Tree Maximum Path Sum

time: O(n)

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

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

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

還有 res 是獨立計算的

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