Binary Tree Maximum Path Sum

Problem

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

Example

Given the below binary tree:

      1
     / \
    2   3

return 6.

Solution

DP.

Create a method to return the max sum of a single chain that is up to this node, so it is either the value of this node node.val or max(left + right) + node.val.

The overall max sum is either the value of this single node node.val or the sum of the max left and max right and the current node value maxPath(node.left) + maxPath(node.right) + node.val.