# binary-tree-maximum-path-sum

## Problem

Binary Tree Maximum Path Sum

## 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.

• iterate right subtree, `if right < 0`, discard right value, keep 0.

• compute maximum value (3 possible calculations)

• `max = max(max, left + right + node.val)`

• `return max(left, right) + node.val;`

### Code

Code with global parameter

``````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

``````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;
}
}
}``````

Last updated