# Binary Tree Maximum Path Sum

## What will the maximum path look like

Though paths can be starting from any node and end at any node, the appearances only can be:

- Appearance 1

```
*
/ \
* *
/ \
* *
/ \
S *
\
E
```

- Appearance 2

```
E
/
*
/
*
/
S
```

- Appearance 3

```
S
\
*
\
*
\
*
\
E
```

### Note

Appearances above are only talking about `TRUNK`

.

Treat the path below as Appearance 1

```
*
/ \
* *
/ \
* *
\ /
S *
\
E
```

## Tree Version of Maximum Subarray

- Appearance 2/3

These two appearances are easy to understand and to build a path, just take the maximum node.
like `Maximum Subarray`

, if the sum goes below `0`

, forget the old nodes.

- Appearance 1

If a node's left child or right child is less than `0`

, drop it, then the node becomes `Appearance 2/3`

.

If both the left child and right child are positive, just add them together, `maxPathSum(node.left) + node.val + maxPathSum(node.right)`

will be the `maxPathSum`

which contains that node.

## Put them together

As we know how to find the `maxPathSum`

of any node, we can go through the tree and update the max value.

### Source code *Read on Github*

```
1 /**
2 * Definition for binary tree
3 * public class TreeNode {
4 * int val;
5 * TreeNode left;
6 * TreeNode right;
7 * TreeNode(int x) { val = x; }
8 * }
9 */
10 public class Solution {
11
12 int max;
13
14 int sum(TreeNode root){
15 if(root == null) return 0;
16
17 int left = sum(root.left);
18 int right = sum(root.right);
19
20 left = Math.max(left, 0);
21 right = Math.max(right, 0);
22
23 int sum = root.val + left + right;
24 max = Math.max(max, sum);
25
26 return Math.max(left, right) + root.val;
27 }
28
29 public int maxPathSum(TreeNode root) {
30
31 max = Integer.MIN_VALUE;
32 sum(root);
33
34 return max;
35 }
36 }
```