# binary-tree-maximum-path-sum

## Problem

[Binary Tree Maximum Path Sum](https://leetcode.com/explore/featured/card/30-day-leetcoding-challenge/532/week-5/3314/)

## Problem Description

```
Given a non-empty binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

Example 1:
Input: [1,2,3]
  1
 / \
2   3

Output: 6 (1+2+3)

Example 2:
Input: [-10,9,20,null,null,15,7]
  -10
   / \
  9  20
    /  \
   15   7

Output: 42(15+20+7)
```

## Solution

For this problem, we can define a global parameter max and init max = Integer.MIN\_VALUE; personally do not like it, in real industry project, not recommend this way though. Personally perfer to define a class (object) to hold max value. below will post both code.

As problem described, maximum path sum go be left subtree, right subtree, or include left subtree + right subtree + root.val.

Recursively iterate subtree,

* iterate left subtree,`if left < 0`, discard left value, keep 0.&#x20;
* iterate right subtree, `if right < 0`, discard right value, keep 0.&#x20;
* compute maximum value (3 possible calculations)
* `max = max(max, left + right + node.val)`
* `return max(left, right) + node.val;`

### Code

**Code with global parameter**

```java
class Solution {
    private int max = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        if (root == null) return 0;
        helper(root);
        return max;
    }

    private int helper(TreeNode node) {
        if (node == null) return 0;
        int left = Math.max(0, helper(node.left));
        int right = Math.max(0, helper(node.right));
        // cross root value
        max = Math.max(max, left + right + node.val);
        // return left or right subtree maximum value and extend to root
        return Math.max(left, right) + node.val;
    }
}
```

**Code with class to hold object**

```java
class Solution {
    public int maxPathSum(TreeNode root) {
        if (root == null) return 0;
        return helper(root).res;
    }

    private Result helper(TreeNode root) {
        if (root == null) return new Result(0, Integer.MIN_VALUE);
        Result left = helper(root.left);
        Result right = helper(root.right);
        int max = Math.max(0, Math.max(left.max, right.max)) + root.val;
        int arch = Math.max(0, left.max) + Math.max(0, right.max) + root.val;
        int res = Math.max(Math.max(max, arch), Math.max(left.res, right.res));
        return new Result(max, res);
    }

    class Result {
       int max;
       int res;
       public Result(int max, int res) {
           this.max = max;
           this.res = res;
       }                    
    }
}
```


---

# 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://snowan.gitbook.io/study-notes/leetcode/30daychallenge/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.