# Binary Tree Maximum Path Sum

ID: 94; medium

## Solution 1 (Java)

``````/**
* Definition of TreeNode:
* public class TreeNode {
*     public int val;
*     public TreeNode left, right;
*     public TreeNode(int val) {
*         this.val = val;
*         this.left = this.right = null;
*     }
* }
*/

public class Solution {

private int maxPathSum = Integer.MIN_VALUE;

/**
* @param root: The root of binary tree.
* @return: An integer
*/
public int maxPathSum(TreeNode root) {
dfs(root);
return maxPathSum;
}

private int dfs(TreeNode root) {
if (root == null)
return 0;

int left = dfs(root.left);
int right = dfs(root.right);

maxPathSum = Math.max(maxPathSum, left + root.val);
maxPathSum = Math.max(maxPathSum, right + root.val);
maxPathSum = Math.max(maxPathSum, root.val);
maxPathSum = Math.max(maxPathSum, left + right + root.val);

return Math.max(Math.max(left, right), 0) + root.val;
}
}``````

### Notes

There are 4 types of paths that can be candidates for the maximum path sum.

1. Max path of left tree + root

2. Max path of right tree + root

3. Only the root

4. Max single path of left tree + root + max single path of right tree

Last updated